#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
 
using namespace std;
 
long long powmod(long long x, long long y, long long m) {
    long long ans = 1;
    
    while (y) {
        if (y & 1) ans = (__int128)ans * x % m;
        
        x = (__int128)x * x % m;
        y >>= 1;
    }
    
    return ans;
}
 
bool suspect(long long a, int s, long long d, long long n) {
    long long x = powmod(a, d, n);
    
    if (x == 1) return true;
    
    for (int i = 0; i < s; i++) {
        if (x == n - 1) return true;
        
        x = (__int128)x * x % n;
    }
    
    return false;
}
 
bool isprime(long long n) {
    long long d = n - 1, s = 0;
    int test[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    
    if (n <= 1 || (n > 2 && n % 2 == 0)) return false;
    
    while (d % 2 == 0) {
        s++;
        d /= 2;
    }
    
    for (int i = 0; i < 9; i++) {
        if (test[i] == n) return true;
        if (suspect(test[i], s, d, n) == false) return false;
    }
    
    return true;
}
 
long long a[100000];
int b[1000001];
 
int main() {
    int n, ans = 0, sum = 0, i;
    long long j;
    vector <int> v;
    map <vector <pair<long long, int> >, int> mp;
    map <vector <pair<long long, int> >, int>::iterator it;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) scanf("%lld", &a[i]);
    
    for (i = 2; i <= 1000000; i++) {
        if (b[i] > 0) continue;
        
        b[i] = i;
        v.push_back(i);
        
        for (j = (long long)i * i; j <= 1000000; j += i) {
            if (b[j] == 0) b[j] = i;
        }
    }
    
    for (i = 0; i < n; i++) {
        vector <pair<long long, int> > w;
        
        if (isprime(a[i])) {
            w.push_back(make_pair(a[i], 1));
        } else {
            long long x = sqrt(a[i]);
            
            if (x * x == a[i]) {
                while (x > 1) {
                    if (w.size() >= 1 && w.back().first == b[x]) {
                        if (w.back().second == 1) {
                            w.pop_back();
                        } else {
                            w.back().second = 1;
                        }
                    } else {
                        w.push_back(make_pair(b[x], 2));
                    }
                    
                    x /= b[x];
                }
            } else {
                for (j = 0; j < v.size() && a[i] > 1; j++) {
                    if (a[i] % v[j] == 0) {
                        int c = 0;
                        
                        while (a[i] % v[j] == 0) {
                            c++;
                            a[i] /= v[j];
                        }
                        
                        c %= 3;
                        
                        if (c > 0) w.push_back(make_pair(v[j], c));
                        
                        if (a[i] <= 1000000) break;
                        
                        if (isprime(a[i])) {
                            w.push_back(make_pair(a[i], 1));
                            a[i] = 1;
                        }
                    }
                }
                
                while (a[i] > 1) {
                    if (w.size() >= 1 && w.back().first == b[a[i]]) {
                        if (w.back().second == 2) {
                            w.pop_back();
                        } else {
                            w.back().second++;
                        }
                    } else {
                        w.push_back(make_pair(b[a[i]], 1));
                    }
                    
                    a[i] /= b[a[i]];
                }
            }
        }
        
        mp[w]++;
    }
    
    for (it = mp.begin(); it != mp.end(); it++) {
        if (it->first.size() == 0) {
            ans++;
        } else {
            vector <pair<long long, int> > w;
            
            for (j = 0; j < it->first.size(); j++) w.push_back(make_pair(it->first[j].first, 3 - it->first[j].second));
            
            if (mp.count(w)) {
                sum += max(it->second, mp[w]);
            } else {
                ans += it->second;
            }
        }
    }
    
    printf("%d\n", ans + sum / 2);
    
    return 0;
}


Measured memory_bytes: 19832