問題文

長さ $n$ の正整数列 $\{a_i\}$ が与えられます。

$\sqrt{\prod_{i \in I} a_i} \in \mathbb{Z}$ を満たす区間 $I=[l, r] (1 \le l \le r \le n)$ を数え上げてください。

制約

• $1 \le n \le 2 \times 10^5$
• $1 \le a_i \le 10^6$
• 入力はすべて整数

入力

$n$
$a_1\ a_2\ \dots\ a_n$

出力

答えを出力してください。最後に改行してください。

サンプル

6
1 5 6 15 2 2

4

10
1 2 3 4 5 6 7 8 9 10

3