Power Divisors

（難易度目安:点)

長さの自然数のみから構成される数列に対し、以下を満たす自然数のペアの個数はいくつ存在するか答えてください。

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

・

・

・入力はすべて整数

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

N 
A_1 A_2 ... A_N

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

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

3
2 3 4

2

この時、ペアは全てでの通り考えられ、それぞれ得られる数はとなります。

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

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

4
1 1 2 2

5

この時として考えられる値はの通りであり、それぞれの約数の個数はとなります。

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

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

59