#include <algorithm> #include <bitset> #include <iostream> #include <map> #include <vector> using namespace std; using i64 = long long; constexpr int PRIME_MAX = 1260; // 1260 ** 3 > 2e9 vector<int> p3; void get_p3() { bitset<PRIME_MAX + 5> not_prime(3); for (int i = 2; i <= PRIME_MAX; ++i) { if (not_prime[i]) continue; p3.emplace_back(i * i * i); for (int j = i * i; j <= PRIME_MAX; j += i) not_prime[j] = true; } } int reduce(i64 n) { for (int x : p3) { while (n % x == 0) n /= x; if (n < x) break; } return n; } int main() { get_p3(); int n; vector<int> arr; map<i64, int> cnts; cin >> n; for (int i = 0; i < n; ++i) { int x; cin >> x; ++cnts[reduce(x)]; } int ans = 0; for (auto& [x, cnt] : cnts) { if (x == 1) ++ans; else { int match = reduce(x * x); ans += max(cnts[match], cnt); cnts[match] = cnt = 0; } } cout << ans << '\n'; return 0; }