题目描述

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

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

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

输入格式

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

$N$ $s_1$ : $s_N$

输出格式

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

题目大意

给定 $n$ 个数 $s_i$，要求从中选出最多的数，满足任意两个数之积都不是完全立方数。$n\le 10^5$，$s_i\le 10^{10}$。

8
1
2
3
4
5
6
7
8

6

6
2
4
8
16
32
64

3

10
1
10
100
1000000007
10000000000
1000000009
999999999
999
999
999

9

提示

制約

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

Sample Explanation 1

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