小杨有一个包含 n 个正整数的序列 A=[a_1,a_2,\ldots,a_n]。

小杨想知道有多少对 \langle l,r\rangle(1\leq l\leq r\leq n) 满足 a_l\times a_{l+1}\times\ldots\times a_r 为完全平方数。

一个正整数 x 为完全平方数当且仅当存在一个正整数 y 使得 x=y\times y。

第一行包含一个正整数 n，代表正整数个数。

第二行包含 n 个正整数 a_i，代表序列 A。

输出一个整数，代表满足要求的 \langle l,r\rangle 数量。

样例解释

满足条件的 \langle l,r\rangle 有  \langle 1,5\rangle 和 \langle 3,3\rangle。

|20\%|n \leq 10^5|1\leq a_i\leq 2

|40\%|n \leq 100|1\leq a_i\leq 30

|40\%|n \leq 10^5|1\leq a_i\leq 30