#include <iostream> #include <map> #define int long long using namespace std; const int maxn = 100005; map<int, int> mp; bool is_p[maxn]; int prime[maxn], a[maxn], cnt = 1, m; int ans; void Era() { is_p[0] = is_p[1] = 0; for (int i = 2; i <= 1260; i++) is_p[i] = 1; for (int i = 2; i <= 1260; i++) { if (is_p[i]) prime[cnt++] = i * i * i; for (int j = i * 2; j <= 1260; j += i) { is_p[j] = 0; } } } int rebuild(int x) { for (int i = 1; i < cnt; ++i) { // cout << prime[i] << endl; while (x % prime[i] == 0) { x /= prime[i]; } if (prime[i] > x) { break; } } return x; } signed main() { // freopen("T3.in", "r", stdin); // freopen("T3.out", "w", stdout); int n; cin >> n; Era(); for (int i = 1, x; i <= n; i++) { cin >> x; x = rebuild(x); mp[x]++; } for (auto& [x, cnt] : mp) { if (x == 1) ++ans; else { int match = rebuild(x * x); ans += max(mp[match], cnt); mp[match] = cnt = 0; } } cout << ans << endl; // fclose(stdin); // fclose(stdout); return 0; }