// Slower C++ solution:
#include<bits/stdc++.h>

//#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef double db;

typedef long double ldb;

#define rep(i,a,b) for(i=a;i<b;i++)

#define repu(i,a,b) for(i=a;i<=b;i++)

#define repd(i,a,b) for(i=a;i>=b;i--)

#define repc(i,a,b,c) for(i=a;i<b;i+=c)

#define repcu(i,a,b,c) for(i=a;i<=b;i+=c)

#define repcd(i,a,b,c) for(i=a;i>=b;i-=c)

#define FIN freopen("input.in","r",stdin)

#define FOUT freopen("output.out","w",stdout)

#define CC(a) memset(a,0,sizeof(a))

#define MST(a,b) memset(a,b,sizeof(a))

#define PII pair<int,int>

#define PLL pair<long long,long long>

#define VI vector<int>

#define VL vector<long long>

#define VII vector<PII>

#define VLL vector<PLL>

#define all(x) x.begin(),x.end()

#define mp make_pair

#define pb push_back

#define pf push_front

#define fi first

#define se second



template<typename T>inline void gn(T &x){

	x=0;T f=1;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	x*=f;

}

template<typename T>inline void gt(T x){

	if(!x)return;

	gt(x/10);putchar(x%10+'0');

}



const LL N=100005;

struct NODE{

	LL a,b,c;

}tt[N];

LL t,n,m,ans;

LL MOD=1e9+7,inf=0x1f1f1f1f;

db eps=1e-5;

LL ff[N],fac[N],a,b;

LL pr[N/10];

bitset<N> prime;

map<LL,LL> ma,mb;

set<LL> v;



void getprime(){

	LL i,j,k,l;

	for(i=2;i<N;i++){

		if(!prime[i]){

			pr[++pr[0]]=i;

			for(j=i+i;j<N;j+=i)prime[j]=1;

		}

	}

//	cout<<pr[0]<<endl;

}



LL cmp(NODE a,NODE b){

	return a.a<b.a;

}



LL check(LL x){

	LL i,j,k,l,cnt;

	a=b=1;

	for(i=1;i<=pr[0]&&pr[i]*pr[i]<=x;i++){

		if(x%pr[i]==0){

			cnt=0;

			while(x%pr[i]==0){

				x/=pr[i];

				cnt++;

			}

			cnt%=3;

			if(cnt==1){

				a*=pr[i];

				b*=pr[i]*pr[i];

			}

			else if(cnt==2){

				a*=pr[i]*pr[i];

				b*=pr[i];

			}

		}

	}

	if(x>1){

		a*=x;b*=x*x;

	}

	if(b<0||b>1e10)return 0;

	else return 1;

}



int main()

{

	ios_base::sync_with_stdio(false);cin.tie(0);

	LL i,j=0,k,l,ca=0;

	getprime();

	cin>>n;

	repu(i,1,n)cin>>ff[i];

	sort(ff+1,ff+n+1);

	repu(i,1,n){

		if(ff[i]!=ff[i-1]){

			if(check(ff[i])){

				tt[++j].a=a;

				tt[j].b=b;

				tt[j].c++;

			}

			else {

				ans++;

			}

		}

		else {

			if(b<0||b>1e10){

				ans++;

			}

			else {

				tt[j].a=a;

				tt[j].b=b;

				tt[j].c++;

			}

		}

	}

	sort(tt+1,tt+j+1,cmp);

	k=-1;

	repu(i,1,j){

		if(tt[i].a!=tt[i-1].a){

			tt[++k].a=tt[i].a;

			tt[k].b=tt[i].b;

			tt[k].c=tt[i].c;

			ma[tt[i].a]=tt[i].c;

		}

		else {

			tt[k].c+=tt[i].c;

			ma[tt[i].a]+=tt[i].c;

		}

	}

	repu(i,0,k){

		if(tt[i].a==1&&tt[i].c>0){

			ans++;

		}

		else if(ma[tt[i].a]){

			ans+=max(tt[i].c,ma[tt[i].b]);

			ma[tt[i].a]=ma[tt[i].b]=0;

		}

	}

	

	cout<<ans<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.5725144502741892x):
#include<bits/stdc++.h>

//#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long LL;

#define rep(i,a,b) for(i=a;i<b;i++)

#define repu(i,a,b) for(i=a;i<=b;i++)



const LL N=2505;

LL t,n,m,ans;

LL pr[N];

bitset<N> prime;

map<LL,LL> ma;



void getprime(){

	LL i,j,k,l;

//	cout<<pow(1e10,1.0/3.0)<<endl;

	for(i=2;i<N;i++){

		if(!prime[i]){

			pr[++pr[0]]=i;

			for(j=i+i;j<N;j+=i)prime[j]=1;

		}

	}

//	cout<<pr[0]<<endl;

	for(i=1;i<=pr[0];i++){

		pr[i]=pr[i]*pr[i]*pr[i];

	}

}

 

int main()

{

	ios_base::sync_with_stdio(false);cin.tie(0);

	LL i,j,k,l,ca=0;

	getprime();

	cin>>n;

	repu(i,1,n){

		cin>>k;

		for(j=1;j<=pr[0]&&pr[j]<=k;j++){

			while(k%pr[j]==0)k/=pr[j];

		}

		ma[k]++;

	}

	for(auto &p:ma){

		if(p.first==1ll)ans+=min(1ll,p.second);

		else {

			k=1ll*p.first*p.first;

			for(i=1;i<=pr[0]&&pr[i]<=k;i++)while(k%pr[i]==0)k/=pr[i];

			ans+=max(p.second,ma[k]);

			p.second=ma[k]=0ll;

		}

	}

	cout<<ans<<endl;

	return 0;

}