该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

wjw 家里屯了非常多的零食，他家里一共有 $n$ 种零食，根据 wjw 自己订制的各种规则，最后依次排成一排放在一个大柜子里

现在 wjw 觉得 $n$ 种零食摆成一排太占地方了，于是他准备买一些零食柜将这 $n$ 种零食分开存放

这种零食柜非常神奇，只要存在这个零食柜里的零食满足一定的条件，里面的零食将永不过期！

条件是这样的：如果每种零食都有一个特殊的存储值 $a_i$，只要某个零食柜里的任意两种零食的存储值之积不是完全平方数（这里我们认为 $1$ 也是完全平方数），那么这个零食柜里的零食将永不过期

但是 wjw 很懒，他不想改变他好不容易排成一排的零食顺序，所以他只想把这 $n$ 个零食分成好几段，每段零食都用一个零食柜存储

现在 wjw 想知道，他最少需要买几个神奇零食柜？

输入格式

输入第一行包含一个正整数 $n$，表示有 $n$ 种零食 接下来一行包含 $n$ 个整数 $a_i$，分别表示每种零食的存储值 $a_i$

输出格式

输出一个整数，表示 wjw 最少需要购买的神奇零食柜数量

数据范围

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

样例输入

5
9 2 2 3 1

样例输出

2

样例解释

分成两段：$[9,2],[2,3,1]$