B-石老板腾云驾雾_第二届天元编程邀请赛（提高组）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

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

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

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

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

输入描述:

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

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

输出描述:

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

示例1

输入

复制

5
1 1 2 3 4

输出

复制

说明

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

示例2

输入

复制

7
1 3 2 5 4 9 1

输出

复制

备注:

对于 $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$

大样例链接: https://pan.baidu.com/s/1uR8keXNeZmYLN46rMZ0Mfg 密码: a3tl