提示信息：

完全平方数：可以表示为某个整数的平方的数。
例如：4（22）、9（32）、16（42） 都是完全平方数。
子序列：某个序列通过去除任意数量（包括 0 个）的元素但不破坏剩余元素的相对位置而形成的新序列。
例如：原序列为 [1，2，3，4，5，6]；[2，3，6]、[1，2，3]、[1，5] 等都是原序列的子序列。

题目描述：

给定长度为 n 的整数序列 A，请从中选取一个最长的子序列，使得子序列中任意两个数的乘积均为完全平方数。并输出该子序列的长度。

例如：n = 5，整数序列为 [2，8，3，18，12]；其中满足题目要求且长度最长的子序列为 [2，8，18]，长度为 3。

输入描述：

第一行输入一个整数 n（1≤n≤105），表示序列的长度； 第二行输入 n 个整数 Ai（1≤Ai≤106），整数之间以一个空格隔开。输出描述：输出一个整数，表示满足题目要求的最长子序列的长度。

5
2 8 3 18 12

3

Limitation

1s, 1024KiB for each test case.