#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 100001;

int n, r, c[N];
vector<ll> p;
map<ll, ll> o;
map<vector<ll>, int> mp;

int main(){
    for(int i = 2; i < N; i++){
        if(c[i]) continue;
        p.push_back(ll(i));
        o[ll(i) * i] = i;
        o[i] = ll(i) * i;
        for(int j = 2 * i; j < N; j += i) c[j] = 1;
    }
    p.push_back(N);
    scanf("%d", &n);
    for(ll x; n--; ){
        scanf("%lld", &x);
        for(ll i = 2; i * i * i <= x; i++)
            while(x % (i * i * i) == 0) x /= (i * i * i);
        vector<ll> v;
        for(int i = 0; p[i] < 2500; i++){
            if(x % (p[i] * p[i]) == 0){
                x /= (p[i] * p[i]);
                v.push_back(p[i] * p[i]);
            }
            else if(x % p[i] == 0){
                x /= p[i];
                v.push_back(p[i]);
            }
        }
        if(o.find(x) != o.end()){ v.push_back(x); x = 1; }
        if(x >= N){ r++; continue; }
        mp[v]++;
    }
    for(auto &i : mp){
        vector<ll> c;
        for(ll j : i.first) c.push_back(o[j]);
        if(i.first == c){ r++; continue; }
        if(mp.find(c) != mp.end()){
            r += max(i.second, mp[c]);
            i.second = mp[c] = 0;
        }
        r += i.second;
    }
    printf("%d\n", r);
}