#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N;
int64 S[MAXN],pre[1000005];
int prime[MAXN],tot,cnt;
bool nonprime[MAXN];
map<int64,int> zz;
int s[7] = {4,7,11,29,47,71,87};
vector<int64> v;
int64 mul(int64 a,int64 b,int64 MOD) {
    int64 res = 0,t = a;
    while(b) {
	if(b & 1) res = (res + t) % MOD;
	t = (t + t) % MOD;
	b >>= 1;
    }
    return res;
}
int64 fpow(int64 a,int64 c,int64 MOD) {
    int64 res = 1,t = a;
    while(c) {
	if(c & 1) res = mul(res,t,MOD);
	t = mul(t,t,MOD);
	c >>= 1;
    }
    return res;
}
bool check(int64 s,int t,int64 MOD) {
    if(s == 1) return true;
    for(int i = 1 ; i <= t ; ++i) {
	int64 nxt = mul(s,s,MOD);
	if(nxt == 1) {
	    if(s == MOD - 1) return true;
	    return false;
	}
    }
    return false;
}
bool miller_rabin(int64 x) {
    int t = 0;int64 tmp = x - 1;
    while(tmp % 2 == 0) {++t;tmp /= 2;}
    for(int i = 0 ; i < 7 ; ++i) {
	if(!check(fpow(s[i],tmp,x),t,x)) return false;
    }
    return true;
}
void Solve() {
    read(N);
    for(int64 i = 1 ; i <= 1000000 ; ++i) pre[i] = i * i * i;
    for(int64 i = 2 ; i <= 100000 ; ++i) {
	if(!nonprime[i]) {
	    prime[++tot] = i;
	}
	for(int j = 1 ; j <= tot ; ++j) {
	    if(i * prime[j] > 100000) break;
	    nonprime[i * prime[j]] = 1;
	    if(i % prime[j] == 0) break;
	}
    }
    int ans = N;
    for(int i = 1 ; i <= N ; ++i) {
	read(S[i]);
	for(int j = 1 ; j <= 500 ; ++j) {
	    if(pre[prime[j]] > S[i]) break;
	    while(S[i] % pre[prime[j]] == 0) S[i] /= pre[prime[j]];
	}
	if(S[i] == 1) ++cnt;
	else {zz[S[i]]++;v.pb(S[i]);}
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    if(cnt > 1) ans -= (cnt - 1);
    for(auto num : v) {
	int64 t = sqrt(num);
	if(t * t == num) continue;
	if(num <= 100000 && !nonprime[num]) {ans -= min(zz[num],zz[num * num]);}
	else {
	    int64 x = num;
	    int64 op = 1;
	    for(int i = 1 ; i <= 500 ; ++i) {
		if(prime[i] > 3500 || prime[i] > x) break;
		if(x % prime[i] == 0) {
		    int c = 0;
		    while(x % prime[i] == 0) {x /= prime[i];++c;}
		    c = 3 - c;
		    op = op * prime[i];
		    if(op > 1e10) goto fail;
		    if(c == 2) op = op * prime[i];
		    if(op > 1e10) goto fail;
		}
	    }
	    if(x != 1) {
		if(x <= 100000) {
		    if(nonprime[x]) goto fail;
		    for(int i = 0 ; i < 2 ; ++i) {
			op = op * x;
			if(op > 1e10) goto fail;
		    }
		}
		else {
		    int64 t = sqrt(x);
		    if(t * t != x) goto fail;
		    else {
			op = op * t;
			if(op > 1e10) goto fail;
		    }
		}
	    }
	    
	    if(op > num) ans -= min(zz[num],zz[op]);
	}
        fail:;
    }
    out(ans);enter;
}

int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}


Measured memory_bytes: 20084