配点 : $1100$ 点

問題文

高橋君は誕生日にお母さんから正の整数 $s_1,...,s_N$ をもらいました。ただし、要素の重複は許されます。 高橋君は、これらの$N$個の整数のうちのいくつかを丸で囲みます。

高橋君は立方数が嫌いなので、$s_i,s_j(i \neq j)$の両方が丸で囲まれているなら、その積$s_is_j$は立方数とならないようにしたいです。 例えば、$s_1=1,s_2=1,s_3=2,s_4=4$のとき、$s_1$と$s_2$を同時に丸で囲むことはできません。また、$s_3$と$s_4$を同時に丸で囲むこともできません。

高橋君が丸で囲むことができる整数の個数の最大値を求めてください。

制約

• $1 \leq N \leq 10^5$
• $1 \leq s_i \leq 10^{10}$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$s_1$

:

$s_N$

出力

高橋君が丸で囲むことができる整数の個数の最大値を表す整数を出力せよ。

8
1
2
3
4
5
6
7
8

6

$1,2,3,5,6,7$ を丸で囲むことができます。

6
2
4
8
16
32
64

3

10
1
10
100
1000000007
10000000000
1000000009
999999999
999
999
999

9