Description

有$n$个正整数，第$i$个为$a_i$。

求有多少个正整数对$(l,r)$满足$1\le l\le r\le n$且$\prod_{i=l}^{r}a_i$是完全平方数，即求有多少个区间满足区间内所有数的乘积是完全平方数。

Input Format

从 square.in 读入数据

第一行一个正整数$n$。

第二行$n$个正整数，第$i$个为$a_i$。

Output Format

向 square.out 输出数据

输出一个非负整数，表示答案。

Sample

样例输入1

4
2 2 3 3

样例输出1

3

Hint

对于前$10\%$的数据，$n,a_i\le10$。

对于前$30\%$的数据，$n,a_i\le100$。

对于前$50\%$的数据，$n,a_i\le1000$。

对于前$70\%$的数据，$n,a_i\le10000$。

对于$100\%$的数据，$n,a_i\le100000$。