// Original C++ solution (slower):
#include <bits/stdc++.h>

#define ll long long

using namespace std;



const int N = 1e5+10;

ll a[N],b[N],primes[N];

int n,vis[N],k;

map<ll,int>mp;



void init(){

    k = 0;

    for(ll i = 2; i*i*i <= 1e10; i ++){

        int flag = 0;

       for(int j = 2; j <= i/2; j ++) if(i%j==0){flag=1;break;}

       if(flag==0) primes[k++] = i;

    }

}



ll sqr(ll x){

    return x*x;

}



int main(){

    init();

    scanf("%d",&n);

    for(int i = 1; i <= n; i ++){

        ll x; scanf("%lld",&x);

        for(int j = 0; j < k; j ++){

            ll tmp = primes[j]*primes[j]*primes[j];

            if(tmp > x) break;

            while(x % tmp == 0) x /= tmp;

        }

        mp[x] ++; a[i] = x;

        ll y = 1;

        for(int j = 0; j < k; j ++){

            ll tmp = primes[j]*primes[j]*primes[j];

            if(tmp > x) break;

            if(x % primes[j] == 0){

                y *= (x % (primes[j]*primes[j]) == 0) ? primes[j] : primes[j]*primes[j];

                while(x % primes[j] == 0) x /= primes[j];

            }

        }

        if(sqr((ll)sqrt(x)) == x) y *= (ll)sqrt(x);

        else y *= x*x;

        b[i] = y;

    }

    int ans = 0;

    if(mp[1]) ans ++, mp[1] = 0;

    for(int i = 1; i <= n; i ++){

        ans += max(mp[a[i]],mp[b[i]]); mp[a[i]] = mp[b[i]] = 0;

    }

    printf("%d\n",ans);

    return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;

const int maxn = 100000 + 100;

typedef long long int lli;

typedef pair<lli, lli> pii;

pii a[maxn];

bool isPrime[maxn];

int plist[maxn], pnum = 0;



map<lli, int> mp;



int main() {

//    freopen("xx/01.in", "r", stdin);

    isPrime[0] = 1;

    isPrime[1] = 1;

    for (int i = 2; i <= 4000; i++) {

        if (!isPrime[i]) {

            pnum++;

            plist[pnum] = i;

        }

        for (int j = 1; j <= pnum; j++) {

            if (i * plist[j] > 4000)

                break;

            isPrime[i * plist[j]] = 1;

            if (!(i % plist[j]))

                break;

        }

    }

    int n, ans = 0;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {

        scanf("%lld", &a[i].first);

        lli tmp = a[i].first;

        a[i].first = 1;

        a[i].second = 1;

        for (int j = 1; j < pnum && 1ll * plist[j] * plist[j] * plist[j] <= tmp; j++) {

            int cnt = 0;

            while (tmp % (1ll * plist[j] * plist[j] * plist[j]) == 0) {

                tmp /= (1ll * plist[j] * plist[j] * plist[j]);

            }

            while (tmp % plist[j] == 0) {

                tmp /= plist[j];

                cnt++;

            }

            if (cnt == 1) {

                a[i].first *= plist[j];

                a[i].second *= (1ll * plist[j] * plist[j]);

            } else if (cnt == 2) {

                a[i].first *= (1ll * plist[j] * plist[j]);

                a[i].second *= plist[j];

            }

        }

        if (tmp != 1) {

            a[i].first *= tmp;

            lli x = (lli) sqrt(tmp);

            if (x * x == tmp) {

                a[i].second *= x;

            } else if (tmp <= 100000) {

                a[i].second *= (tmp * tmp);

            } else {

                a[i].second = 0;

            }

        }

        mp[a[i].first]++;

    }

    if(mp[1]) ans ++, mp[1] = 0;

    for(int i = 0; i < n; i ++){

        ans += max(mp[a[i].first],mp[a[i].second]);

        mp[a[i].first] = mp[a[i].second] = 0;

    }

    printf("%d\n",ans);

    return 0;

}


// Fastest known solution for this problem: