题目描述

张老师的弟弟想买一双新鞋，但是张老师并不想给他买，于是出了一道题考考他。弟弟做了 $114514$ 天还是解决不了，无奈之下来到天元楼请石老板解决这个问题。

石老板正在忙着修复黄金律，他回眸一笑道：”只要有100个褪色者AC了这道题，你姐姐就会帮你买新鞋子”。

现在，作为褪色者的你，请为张老师弟弟的梦想助力。

给定一个长度为 $n$ 的序列 $A$，令 $A$ 中第 $i$ 个元素称为 $A_i$，你现在需要选出一些下标，并且需要使得你选出的这些下标中没有任意一对 $(i,j)$ 下标对应的 $A_i \times A_j$ 是一个平方数，你需要输出你最多能选出多少个下标。

输入样例：

第一行一个数字 $n$ 表示数组长度

第二行 $n$ 个正整数表示给定的 $A$ 序列。

输出样例：

一行一个整数表示最多能选出的下标个数。

样例

输入样例

5
1 1 2 3 4

输出样例

3

样例解释：

选中下标 {2,3,4} 即可，满足选出元素最多的方案可能不止一个。

输入样例

7
1 3 2 5 4 9 1

输出样例

4

ex_prime3.in/ex_prime3.ans 对应下面 $30 \%$ 的数据的数据类型

数据范围：

对于 $30 \%$ 的数据有 ： $n \leq 1000,A_i \leq 10^6$

对于 $60 \%$ 的数据有 ： $n \leq 10^5,A_i \leq 10^6$

对于 $100\%$ 的数据有 ：$1\le n \leq 10^5,1\le A_i \leq 10^9$

样例下载