#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > 
#define pii pair<int,int> 
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define SZ(x) ((int)x.size())
using namespace std;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
const int BufferSize=1<<16;
char buffer[BufferSize],*Bufferhead,*Buffertail;
bool Terminal;
inline char Getchar(){
	if(Bufferhead==Buffertail){
		int l=fread(buffer,1,BufferSize,stdin);
		if(!l){Terminal=1;return 0;}
		Buffertail=(Bufferhead=buffer)+l;
	}
	return *Bufferhead++;
}
template<class T>inline bool read(T &x){
	x=0;char c=Getchar(),rev=0;
	while(c<'0'||c>'9'){rev|=c=='-';c=Getchar();if(Terminal)return 0;}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=Getchar();
	if(c=='.'){
		c=Getchar();double t=0.1;
		while(c>='0'&&c<='9') x=x+(c-'0')*t,c=Getchar(),t=t/10;
	}
	x=rev?-x:x;
	return 1;
}
template<class T1,class T2> inline bool read(T1 &x,T2 &y){return read(x)&read(y);}
template<class T1,class T2,class T3> inline bool read(T1 &x,T2 &y,T3 &z){return read(x)&read(y)&read(z);}
template<class T1,class T2,class T3,class T4> inline bool read(T1 &x,T2 &y,T3 &z,T4 &w){return read(x)&read(y)&read(z)&read(w);}
inline bool reads(char *x){
	char c=Getchar();
	while(c<33||c>126){c=Getchar();if(Terminal)return 0;}
	while(c>=33&&c<=126) (*x++)=c,c=Getchar();
	*x=0;return 1;
}
template<class T>inline void print(T x,const char c='\n'){
	if(!x){putchar('0');putchar(c);return;}
	if(x<0) putchar('-'),x=-x;
	int m=0,a[20];
	while(x) a[m++]=x%10,x/=10;
	while(m--) putchar(a[m]+'0');
	putchar(c);
}
//--------------------------------head---------------------------------------------

const ll inf=1e10;
const int N=200005,M=100005,mod=1e9+7;
template<class T,class S> inline void ch(T &x,const S y){x=(x+y)%mod;}
inline ll mul(ll x,ll y,ll mod){
	ll ans=0;
	while(y){
		if(y&1) ans=(ans+x)%mod;
		x=x*2%mod;y>>=1;
	}return ans;
}
inline ll exp(ll x,ll y,const ll mod=::mod){
	int ans=1;
	while(y){
		if(y&1) ans=mul(ans,x,mod);
		x=mul(x,x,mod);y>>=1;
	}return ans;
}

int p[N],tot,n,ans,c11;
map<ll,int> c;

inline bool check(ll x){
	if(exp(2,x-1,x)!=1) return 0;
	if(exp(3,x-1,x)!=1) return 0;
	if(exp(5,x-1,x)!=1) return 0;
	if(exp(7,x-1,x)!=1) return 0;
	if(exp(11,x-1,x)!=1) return 0;
	return 1;
}

void calc(){
	ll x,a=1,b=1;read(x);
	for(int j=1;j<=tot;j++){
		int p=::p[j],cnt=0;
		while(x%p==0) x/=p,cnt=(cnt+1)%3;
		if(cnt){
			for(int k=0;k<cnt;k++) a*=p;
			for(int k=0;k<3-cnt;k++){
				b*=p;
				if(b>inf){ans++;return;}
			}
		}
	}
	if(x>100000&&check(x)){ans++;return;}
	if(x>1&&x<=100000){
		a*=x;b*=x;if(b>inf){ans++;return;}
		b*=x;if(b>inf){ans++;return;}
	}
	else if(x>100000){
		ll t=sqrt(x)+0.5;
		if(t*t==x) a*=x,b*=t; else{ans++;return;}
	}
	if(a==1){c11=1;return;}
//	dprintf("%lld %lld\n",a,b);
	ans-=max(c[a],c[b]);
	c[a]++;
	ans+=max(c[a],c[b]);
}

int main(){
#ifdef rqgao2014
	assert(freopen("input.txt","r",stdin));
#endif
	read(n);
	for(int i=2;i<=2200;i++){
		bool isok=1;
		for(int j=2;j*j<=i;j++)
			if(i%j==0){isok=0;break;}
		if(isok) p[++tot]=i;
	}
	for(int i=1;i<=n;i++)
		calc();
	printf("%d\n",ans+c11);
	return 0;
}

Measured memory_bytes: 10624