thz 的神奇零食柜
说明
thz 家里屯了非常多的零食，他家里一共有 $n$ 种零食，根据 thz 自己订制的各种规则，最后依次排成一排放在一个大柜子里
现在 thz 觉得 $n$ 种零食摆成一排太占地方了，于是他准备买一些零食柜将这 $n$ 种零食分开存放
这种零食柜非常神奇，只要存在这个零食柜里的零食满足一定的条件，里面的零食将永不过期！
条件是这样的：如果每种零食都有一个特殊的存储值 $a_i$，只要某个零食柜里的任意两种零食的存储值之积不是完全平方数（这里我们认为 $1$ 也是完全平方数），那么这个零食柜里的零食将永不过期
但是 thz 很懒，他不想改变他好不容易排成一排的零食顺序，所以他只想把这 $n$ 个零食分成好几段，每段零食都用一个零食柜存储
现在 thz 想知道，他最少需要买几个神奇零食柜？
输入格式
输入第一行包含一个正整数 $n$，表示有 $n$ 种零食接下来一行包含 $n$ 个整数 $a_i$，分别表示每种零食的存储值 $a_i$
对于 $30\%$ 的数据： $1 \leq n \leq 100, 1 \leq a_i \leq 100$
对于 $60\%$ 的数据： $1 \leq n \leq 100000$
对于 $100\%$ 的数据：$1 \leq n \leq 200000, 1 \leq a_i \leq 10^8$
对于 $60\%$ 的数据： $1 \leq n \leq 100000$
对于 $100\%$ 的数据：$1 \leq n \leq 200000, 1 \leq a_i \leq 10^8$
输出格式
输出一个整数，表示 thz 最少需要购买的神奇零食柜数量样例
5
9 2 2 3 12相关
在下列比赛中: