#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, 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; j <= 1260; j += i) { is_p[j] = 0; } } } int rebuild(int x) { for (int i = 1; i <= cnt; ++i) { 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; for(int i = 0;i < n;i++){ cin >> a[i]; a[i] = rebuild(a[i]); mp[a[i]]++; } for(auto x : mp) { if(x.first == 1) { ans++; continue; } else{ int k = x.first * x.first; ans += max(x.second, mp[k]); mp[k] = 0; x.second = 0; } } cout << ans << endl; // fclose(stdin); // fclose(stdout); return 0; }