分数: 1100 点
问题陈述
Snuke 得到正整数 s_1,...,s_N 来自他母亲,作为生日礼物。可能存在重复的元素。
他会圈出其中一些 N 整数。由于他不喜欢立方数,因此他想确保如果两者 s_i 和 s_j (i ≠ j) 圈出,该产品 s_is_j is 不 立方。例如,当 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
潜弹可以盘旋 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