题面翻译

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

输入格式

第一行给出数字N

接下来N行，每行一个数字

输出格式

如题

样例 #1

样例输入 #1

8
1
2
3
4
5
6
7
8

样例输出 #1

6

样例 #2

样例输入 #2

6
2
4
8
16
32
64

样例输出 #2

3

样例 #3

样例输入 #3

10
1
10
100
1000000007
10000000000
1000000009
999999999
999
999
999

样例输出 #3

9

提示

制約

• $1\ ≦\ N\ ≦\ 10^5$
• $1\ ≦\ s_i\ ≦\ 10^{10}$