問題文

（難易度目安:$400$点)

長さ$N$の自然数のみから構成される数列$A$に対し、以下を満たす自然数のペア$(i,j)(1 \le i < j \le N)$の個数はいくつ存在するか答えてください。

・ $A_iA_j$の約数の個数は$2$の冪乗である。

制約

・$1\le N \le 1000$

・$1\le A_i \le 10^9$

・入力はすべて整数

入力

入力は以下の形式で与えられます。

N 
A_1 A_2 ... A_N

出力

ペアの個数を1行で出力してください。

最後に改行してください。

サンプル

3
2 3 4

2

この時、ペアは全てで$(i,j) = (1,2),(1,3),(2,3)$の$3$通り考えられ、それぞれ得られる数は$(6,8,12)$となります。

このそれぞれに対して約数の個数を数えると$(4,4,6)$であり、$2$の冪乗に等しいものは$2$つ存在します。

したがって、$2$を出力します。

4
1 1 2 2

5

この時$A_iA_j$として考えられる値は$(1,2,2,2,2,4)$の$6$通りであり、それぞれの約数の個数は$(1,2,2,2,2,3)$となります。

このうち、$2$の冪乗に等しいものは$5$つ存在します。

20
452902405 396883670 481861767 674061260 805187376 974697172 198697835 259654289 717370511 155641344 525659558 869302670 185490765 647522638 831270876 761020820 560278586 960923514 270814672 563095766

59