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

小杨想知道有多少对 (l, r) 满足 1 \le l \le r \le n，使得乘积 a_l \times

a_{l+1} \times \dots \times a_r 为完全平方数。

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

从文件 multiply.in 中读入数据。

第一行包含一个正整数 n，代表序列长度。

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

输出到文件 multiply.out 中。

输出一个整数，代表满足要求的 (l, r) 数量。

满足条件的 (l, r) 有：

• (1, 5)：3 \times 2 \times 4 \times 3 \times 2 = 144 = 12^2
• (3, 3)：4 = 2^2

共 2 个。

• 1 \le n \le 10^5
• 1 \le |a_i| \le 30