题目描述

Snuke 从他的母亲那里收到了一系列正整数 $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$。

求 Snuke 最多能够圈出多少个整数。

约束条件

• $1 ≦ N ≦ 10^5$
• $1 ≦ s_i ≦ 10^{10}$
• 所有输入值都是整数。

输入

从标准输入中以以下格式给出输入：

$N$
$s_1$
:
$s_N$

输出

输出 Snuke 最多能够圈出的整数个数。

样例输入 1

8
1
2
3
4
5
6
7
8

样例输出 1

6

Snuke 可以圈出 $1,2,3,5,6,7$。

样例输入 2

6
2
4
8
16
32
64

样例输出 2

3

样例输入 3

10
1
10
100
1000000007
10000000000
1000000009
999999999
999
999
999

样例输出 3

9