stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define FOR(i, s, e) for(int i = (s); i < (e); i++)

#define FOE(i, s, e) for(int i = (s); i <= (e); i++)

#define FOD(i, s, e) for(int i = (s); i >= (e); i--)

#define ll long long



ll A[100005], prime[10005], prime_3[10005];

int n, m, x, y, z, k, w;

int p[10005];



map<ll, int> M;



void find_prime()

{

	FOE(i, 2, 10000)

	{

		if (p[i] == 1) continue;

		for (int j = i * i; j <= 10000; j += i) p[j] = 1;

	}

	

	FOE(i, 2, 10000) if (p[i] == 0) 

	{

		prime[k] = i;

		prime_3[k++] = 1ll * i * i * i;

	}

}



ll inv(ll x)

{

	ll tmp = x, ret = 1ll;

	

	FOR(i, 0, k)

	{

		if (prime_3[i] > tmp) break;

		y = 0;

		while (tmp % prime[i] == 0) 

		{

			tmp /= prime[i];

			y++;

		}

		

		if (y == 1) ret *= prime[i] * prime[i];

		else if (y == 2) ret *= prime[i];

	

		if (ret > 10000000000ll) return -1;

	}

	

	ll t = (ll)sqrt(tmp);

	if (t * t == tmp) ret *= t;

	else ret *= tmp * tmp;

	

	if (ret > 10000000000ll) return -1;

	return ret;

}



int main ()

{

	find_prime();



	scanf("%d", &n);

	FOR(i, 0, n) 

	{

		scanf("%lld", &A[i]);

		FOR(j, 0, k) while (A[i] % prime_3[j] == 0) A[i] /= prime_3[j];

	}

	

	sort(A, A + n);



	x = 0;

	FOR(i, 0, n) 

	{

		x++;

		if (i == n - 1 || A[i] != A[i + 1])

		{

			M.insert(make_pair(A[i], x));

			x = 0;

		}

	}

	

	//FOR(i, 0, n) printf("%lld ", A[i]); printf("\n");

	

	int ans = 0;

	ll tmp;

	

	FOR(i, 0, n)

	{

		if (A[i] == 1) continue;

		if (i > 0 && A[i] == A[i - 1]) continue;

		

	//	printf("%d %d\n", A[i], M.find(A[i]) -> second);

		

		tmp = inv(A[i]);

		

		if (M.find(tmp) == M.end()) ans += M.find(A[i]) -> second;

		else 

		{

			if (tmp < A[i]) continue;

			ans += max(M.find(A[i]) -> second, M.find(tmp) -> second);

		}

	} 

	

	

	if (A[0] == 1) ans++;

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

}


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

using namespace std;

typedef long long i64;



int n, ans;

i64 a[100010], b[100010];



map<i64, int> mp;



i64 square(i64 x)

{

	return x * x;

}



i64 clearCubicFactor(i64 x)

{

	for (i64 i = 2; i * i * i <= x; i++)

		while (x % (i * i * i) == 0)

			x /= (i * i * i);

	return x;

}



int main()

{

	scanf("%d", &n);

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

	{

		i64 x, y = 1;

		scanf("%lld", &x);



		x = clearCubicFactor(x);

		mp[x]++;

		a[i] = x;



		for (i64 j = 2; j * j * j <= x; j++)

			if (x % j == 0)

			{

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

				while (x % j == 0)

					x /= j;

			}



		if (square((i64) sqrt(x)) == x)

			y *= (i64) sqrt(x);

		else

			y *= x * x;

		b[i] = y;

	}

	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", ans);

	return 0;

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

using namespace std;

 

map<long long, long long> cnt;

long long arr[100050];

bool isPrime[3060];

vector<long long> prime;

long long Slove(long long n)

{

    for(vector<long long>::size_type i = 0; i < prime.size(); ++i)

    {

        while(n % prime[i] == 0)

            n /= prime[i];

    }

    return n;

}

int main()

{

    memset(isPrime, true, sizeof(isPrime));

    for(long long i = 2; i <= 3000; ++i)

    {

        if(!isPrime[i])

            continue;

        prime.push_back(i * i * i);

        for(long long j = i + i; j <= 3000; j += i)

            isPrime[j] = false;

    }

    long long n;

    scanf("%lld", &n);

    for(long long i = 1; i <= n; ++i)

        scanf("%lld", &arr[i]);

    for(long long i = 1; i <= n; ++i)

        ++cnt[ Slove(arr[i]) ];

    long long ans;

    if(cnt.find(1) != cnt.end())

        ans = 1;

    else

        ans = 0;

    for(auto it = cnt.begin(); it != cnt.end(); ++it)

    {

        if(it->first == 1)

            continue;

        long long a = it->first;

        long long b = Slove(a * a);

        ans += max(cnt[a], cnt[b]);

        cnt[a] = 0;

        cnt[b] = 0;

    }

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

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1214052989084742x):
#include<map>

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

const int MAX = 2160;

const int MAXN = 100000;

int prm[MAX + 5], pcnt = 0;

bool is_prm[MAX + 5];

void init() {

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

		if( !is_prm[i] )

			prm[++pcnt] = i;

		for(int j=1;i*prm[j]<=MAX;j++) {

			is_prm[i*prm[j]] = true;

			if( i % prm[j] == 0 ) break;

		}

	}

}

ll s[MAXN + 5], a[MAXN + 5], b[MAXN + 5];

ll IsSqr(ll x) {

	ll le = 1, ri = 100000;

	while( le < ri ) {

		ll mid = (le + ri) >> 1;

		if( mid * mid >= x ) ri = mid;

		else le = mid + 1;

	}

	return (ri * ri == x) ? ri : 0;

}

int siz[2*MAXN + 5];

map<ll, int>mp;

int main() {

	init(); int N;

	scanf("%d", &N);

	int ans = 0, flag = false;

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

		a[i] = b[i] = 1;

		scanf("%lld", &s[i]);

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

			int cnt = 0;

			while( s[i] % prm[j] == 0 ) {

				cnt++;

				s[i] /= prm[j];

			}

			cnt %= 3;

			if( cnt == 1 ) {

				a[i] *= prm[j];

				b[i] *= prm[j] * prm[j];

			}

			else if( cnt == 2 ) {

				a[i] *= prm[j] * prm[j];

				b[i] *= prm[j];

			}

		}

		if( IsSqr(s[i]) ) {

			a[i] *= s[i];

			b[i] *= IsSqr(s[i]);

		}

		else {

			a[i] *= s[i];

			b[i] *= s[i] * s[i];

		}

		if( !flag && a[i] == 1 && b[i] == 1 )

			flag = true;

	}

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

		if( a[i] == 1 && b[i] == 1 ) continue;

		if( mp.count(a[i]) )

			siz[mp[a[i]]]++;

		else {

			mp[a[i]] = i;

			mp[b[i]] = i+N;

			siz[i]++;

		}

	}

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

		if( mp[a[i]] == i )

			ans += max(siz[i], siz[i+N]);

	}

	if( flag ) ans++;

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

}
// Slower C++ solution:
#define _USE_MATH_DEFINES

#include <vector>

#include <string>

#include <iostream>

#include <fstream>

#include <sstream>

#include <list>

#include <algorithm>

#include <sstream>

#include <set>

#include <math.h>

#include <cmath>

#include <map>

#include <stack>

#include <queue>

#include <stdio.h>

#include <string.h>

#include <numeric>

 

using namespace std;

 

typedef unsigned long long ll;

 

int N,NP;

 

ll S[100000];

ll prime[100000];

bool is_prime[100001];

 

map <ll, ll> mp;

map <ll,ll>::iterator it;

set <ll> st;

 

int sieve(int n){

  int p=0;

  for(int i=0; i<=n; i++) is_prime[i]=true;

  is_prime[0]=is_prime[1]=false;

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

    if(is_prime[i]){

      prime[p++]=i;

      for(int j=2*i; j<=n; j+=i) is_prime[j]=false;

    }

  }

  return p;

}

 

ll dv(ll x){

 

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

 

    ll q=prime[i]; if(q>1000) break;

    ll t=q*q*q;

    if(t>x) break;

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

 

  }

 

  return x;

 

}

 

ll tp(ll x){

 

  ll y=x*x; //cout<<y<<endl;

 

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

 

    ll q=prime[i]; if(q>1000) break;

    ll t=q*q*q;

 

    if(t>y) break;

 

    while(y%t==0) y/=t;

 

  }

 

  return y;

 

}

 

int main(){

 

 scanf("%d",&N);

 

 NP=sieve(100000);

 

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

 

  scanf("%lld",&S[i]);

  ll x=dv(S[i]);

  mp[x]++;

  

 }

 

 int ans=0;

  

 for(it=mp.begin();it!=mp.end();it++){

 

  ll x=it->first; //cout<<x<<endl;

  ll y=tp(x);

 

  if(st.count(x)) continue;

 

  if(x!=1) ans+=max(mp[x],mp[y]);

  else ans++;

 

  st.insert(y);

 

 }

  

  cout<<ans<<endl;

 

 return 0;

 

}

// Faster C++ solution for the same problem (measured speedup: 1.7703220125807957x):
#define _USE_MATH_DEFINES

#include <vector>

#include <string>

#include <iostream>

#include <fstream>

#include <sstream>

#include <list>

#include <algorithm>

#include <sstream>

#include <set>

#include <math.h>

#include <cmath>

#include <map>

#include <stack>

#include <queue>

#include <stdio.h>

#include <string.h>

#include <numeric>

#define INF 100000000000000LL

 

using namespace std;

 

typedef long long ll;

 

int N;

 

map <ll, int> mp;

map <ll,int>::iterator it;

set <ll> st;

 

ll dv(ll x){

 

  for(ll i=2;; i++){

 

    ll t=i*i*i;

    if(t>x) break;

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

 

  }

 

  return x;

 

}

 

ll tp(ll x){

	ll A=1,B=1;

	for(ll i=2;;i++){

		if(i*i*i>x) break;

		int cnt=0;

		while(x%i==0)

		{

			x/=i;

			cnt++;

		}

		if(cnt==1) A*=i;

		else if(cnt==2) B*=i;

	}

	

      ll dt=(ll) floor(sqrt(x)+0.5);

	if(dt*dt==x) B*=dt;

	else A*=x;

	ll ret=A*B;

	if(ret>INF/A+1) ret=INF;

	else ret*=A;

	return ret;



}

 

int main(){

 

 scanf("%d",&N);

 

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

 

  ll x;

  scanf("%lld",&x);

  x=dv(x);

  mp[x]++;

  //cout<<x<<endl;

 }

 

 int ans=0; //cout<<tp(1027243729)<<endl;

  

 for(it=mp.begin();it!=mp.end();it++){

 

  ll x=it->first; //cout<<x<<endl;

  int cn=it->second;

  ll y=tp(x);

 

  if(st.count(x)) continue;

 

  if(x!=1) ans+=max(cn,mp[y]);

  else ans++;

 

  st.insert(y);

 

 }

  

  cout<<ans<<endl;

 

 return 0;

 

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

using namespace std;

#define ll long long

#define MAX 100100

inline ll read()

{

	ll x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

map<ll,int> M,vis;

int n,tot,ans;

ll a[MAX],b[MAX],p[MAX],pri[MAX];

int main()

{

	n=read();

	for(int i=1;i<=n;++i)a[i]=read();

	for(int i=2;i<=2500;++i)

	{

		bool fl=true;

		for(int j=2;j<i;++j)if(i%j==0){fl=false;break;}

		if(fl)pri[++tot]=i;

	}

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

	{

		p[i]=b[i]=1;

		for(int j=1;j<=tot&&a[i]>1;++j)

			if(a[i]%pri[j]==0)

			{

				int cnt=0;

				while(a[i]%pri[j]==0)a[i]/=pri[j],++cnt;

				cnt%=3;if(!cnt)continue;

				if(cnt==1)p[i]*=1ll*pri[j]*pri[j],b[i]*=pri[j];

				else p[i]*=pri[j],b[i]*=1ll*pri[j]*pri[j];

			}

		if(a[i]==1)continue;

		ll s=sqrt(a[i]);b[i]*=a[i];

		if(s*s==a[i])p[i]*=s;

		else p[i]*=a[i]*a[i];

	}

	for(int i=1;i<=n;++i)++M[b[i]];

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

	{

		if(vis[b[i]])continue;

		if(b[i]!=p[i])ans+=max(M[b[i]],M[p[i]]);

		else ans+=1;

		vis[b[i]]=vis[p[i]]=1;

	}

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

	return 0;

}


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

using namespace std;



int n,p[100010],cnt,vis[100010];

long long a[100010],l[100010],r[100010],ans;//l为原数，r为与l乘积为完全立方数的数 

map<long long,int> mp;

int main()

{

	scanf("%d",&n);

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

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

	vis[1]=1;

	for(int i=2;i<=2200;++i)

	{

		if(!vis[i])

		p[++cnt]=i;

		for(int j=1;j<=cnt&&p[j]*i<=2200;++j)

		{

			vis[p[j]*i]=1;

			if(i%p[j]==0)

			break;

		}

	}

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

	{

		long long ji=a[i],qwq=1,ovo=1;

		for(int j=1;j<=cnt;++j)

		{

			int gg=0;

			while(ji%p[j]==0)

			{

				++gg;

				ji/=p[j];

			}

			gg%=3;

			if(gg)

			{

				for(int k=gg;k<3;++k)

				{

					qwq*=p[j];

					if(qwq>1e10)

					qwq=0;

				}

				while(gg)

				{

					ovo*=p[j];

					--gg;

				}

			}

		}

		l[i]=ovo*ji;

		mp[l[i]]++;

		r[i]=qwq;

		long long qaq=(long long)sqrt(ji);

		if(qaq*qaq!=ji)

		{

			if(ji*r[i]<=1e10)

			r[i]*=ji;

			else

			r[i]=0;

			if(ji*r[i]<=1e10)

			r[i]*=ji;

			else

			r[i]=0;

		}

		else

		{

			if(qaq*r[i]<=1e10)

			r[i]*=qaq;

			else

			r[i]=0;

		}

	}

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

	{

		if(l[i]==1)

		continue;

		ans+=max(mp[l[i]],mp[r[i]]);

		mp[l[i]]=0;

		mp[r[i]]=0;

	}

	if(mp[1])

	ans++;

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

	return 0;

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



using namespace std;



int n;

long long a[100005];

bool ex = false;

multiset<long long> s, ss;

map<long long, int> f;



int spf[100005];



const int MAXN = 100001;



void sieve() {

    spf[1] = 1;

    for (int i=2; i<=100000; i++)

        spf[i] = i;

 	for (int i=4; i<MAXN; i+=2)

        spf[i] = 2;

    for (int i=3; i*i<MAXN; i++)

    {

        if (spf[i] == i)

        {

            for (int j=i*i; j<MAXN; j+=i)

                if (spf[j]==j)

                    spf[j] = i;

        }

    }

}





long long get(long long x) {

	long long ou = 1;

	set<int> vis;

	while (x != 1) {

		if (vis.find(spf[x]) == vis.end()) {

			ou *= spf[x];

			vis.insert(spf[x]);

		}

		x /= spf[x];

	}

	return ou;

}



long long p(long long n) {

	return n*n*n;  

}



signed main() {

	sieve();

	scanf("%d", &n);

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

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

		s.insert(a[i]);

	}

	for (int i = 1; 1ll*i*i*i <= 10000000000; i ++) {

		if (s.find(1ll*i*i*i) != s.end()) {

			ex = true;

			s.erase(1ll*i*i*i);

			ss.insert(1ll*i*i*i);

		}

	}

	//cout << s.size() << endl;

	int res = 0;

	if (ex) res++;

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

		if (ss.find(a[i]) != ss.end()) continue;

		for (int j = 2154; j >= 1; j--) {

			if (a[i] % (1ll*j*j*j) == 0) {

				a[i] /= 1ll*j*j*j;

			}

		}

		f[a[i]]++;

	}

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

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

		if (ss.find(a[i]) != ss.end()) continue;

		//cout << a[i] << endl;

		if (a[i] > 100000) {res += f[a[i]]; f[a[i]] = 0;}

		else {

			long long op = p(get(a[i]))/a[i];

			res += max(f[a[i]], f[op]);

			f[op] = 0;

			f[a[i]] = 0;

		}

	}	

	cout << res;

}

// Faster C++ solution for the same problem (measured speedup: 1.9311440408093874x):
#include<cstdio>

#include<map>

#include<algorithm>

#define N 2200

#define LL long long

#define mod 1000000007

using namespace std;

typedef pair<LL,LL> PLL;

typedef map<LL,int>::iterator miter;

int n,p[N+5],pcnt,ans,cnt0;

bool vis[N+5];

map<LL,int> cnt;

map<LL,LL> iv;

void init()

{

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

	{

		if(!vis[i]) p[++pcnt]=i;

		for(int j=1;i*p[j]<=N;j++)

		{

			vis[i*p[j]]=true;

			if(i%p[j]==0) break;

		}

	}

}

int main()

{

	scanf("%d",&n);

	init();

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

	{

		LL a,tmp,h1=1,inv=1;

		scanf("%lld",&a); tmp=a;

		for(int j=1;j<=pcnt&&1ll*p[j]*p[j]*p[j]<=a;j++)

			if(tmp%p[j]==0)

			{

				int xcnt=0;

				while(tmp%p[j]==0) tmp/=p[j],xcnt++;

				xcnt%=3;

				for(int i=1;i<=xcnt;i++) h1*=1ll*p[j];

				for(int i=1;i<=(3-xcnt)%3;i++) inv*=1ll*p[j];

			}

		if(tmp>1) { h1*=1ll*tmp,inv*=1ll*tmp*tmp; }

		if(h1==1) { cnt0=1; continue; }

		cnt[h1]++;

		iv[h1]=inv,iv[inv]=h1;

	}

	for(miter it=cnt.begin();it!=cnt.end();it++)

		if(cnt.find(iv[it->first])==cnt.end()) ans+=it->second;

		else

		{

			ans+=max(it->second,cnt[iv[it->first]]);

			it->second=cnt[iv[it->first]]=0; 

		}

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

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<cmath>

#define MAXN 100000

#define MAXV 20000

using namespace std;

typedef long long LL;

vector<int> prime;

LL seq[MAXN+5],a[MAXN+5],b[MAXN+5];

bool vis[MAXV+5];

map<LL,int> mp;

void prepare()

{

	for(int i=2;i<=MAXV;i++)

	{

		if(vis[i]==false)

			prime.push_back(i);

		for(int j=0;1LL*prime[j]*i<=MAXV;j++)

		{

			vis[i*prime[j]]=true;

			if(i%prime[j]==0)

				break;

		}

	}

}

void Work(int i,LL x)

{

	a[i]=b[i]=1;

	for(int j=0;1LL*prime[j]*prime[j]*prime[j]<=x;j++)

	{

		LL t1=prime[j],t2=1LL*prime[j]*prime[j],t3=1LL*prime[j]*prime[j]*prime[j];

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

		if(x%t2==0)			a[i]*=t2,b[i]*=t1;

		else if(x%t1==0)	a[i]*=t1,b[i]*=t2;

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

	}

	if(x!=1LL)

	{

		LL t=(LL)sqrt(x);

		if(t*t==x)	a[i]*=x,b[i]*=t;

		else		a[i]*=x,b[i]*=x*x;

	}

}

int main()

{

//	freopen("anticube.in","r",stdin);

//	freopen("anticube.out","w",stdout);

	prepare();

	int N;

	scanf("%d",&N);

	for(int i=1;i<=N;i++)

	{

		scanf("%lld",&seq[i]);

		Work(i,seq[i]);

		mp[a[i]]++;

	}

	int ans=0;

	for(int i=1;i<=N;i++)

		if(mp.find(a[i])!=mp.end())

		{

			if(a[i]==b[i])

			{

				ans++;

				mp.erase(mp.find(a[i]));

			}

			else

			{

				int ansn=mp[a[i]];

				mp.erase(mp.find(a[i]));

				if(mp.find(b[i])!=mp.end())

				{

					ansn=max(ansn,mp[b[i]]);

					mp.erase(mp.find(b[i]));

				}

				ans+=ansn;

			}

		}

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

	return 0;

}

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

using namespace std;

typedef long long ll;



int n,tot,ans;

ll p[3333];

bool tag[3333];

ll a[111111],b[111111];

map<ll,int> m;



void init()

{

    for(int i=2; i<3333; i++)

    {

        if(!tag[i]) p[tot++]=i;

        for(int j=0; j<tot&&i*p[j]<3333; j++)

        {

            tag[i*p[j]]=1;

            if(i%p[j]==0) break;

        }

    }

}



void pre(int id)

{

    ll x=1,y=1;

    for(int i=0; p[i]*p[i]*p[i]<=a[id]; i++)

    {

        int cnt=0;

        while(a[id]%p[i]==0) cnt++,a[id]/=p[i];

        cnt%=3;

        if(cnt==1) x*=p[i],y*=p[i]*p[i];

        else if(cnt==2) x*=p[i]*p[i],y*=p[i];

    }

    if(a[id]!=1)

    {

        x*=a[id];

        ll sq=(ll)sqrt(a[id]);

        if(sq*sq==a[id]) y*=sq;

        else y*=a[id]*a[id];

    }

    a[id]=x,b[id]=y,m[x]++;

}



int main()

{

    init();

    cin>>n;

    for(int i=0; i<n; i++) scanf("%lld",&a[i]),pre(i);

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

    for(int i=0; i<n; i++) if(m[a[i]]) ans+=max(m[a[i]],m[b[i]]),m[a[i]]=m[b[i]]=0;

    cout<<ans;

    return 0;

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

using namespace std;

#define int long long



template <typename T>

void fin(T a){

  cout<<a<<endl;

  exit(0);

}



signed main(){

  std::vector<bool> is_prime(100001,true);

  std::vector<int> pr;

  is_prime[0]=is_prime[1]=false;

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

    if(!is_prime[i])continue;

    pr.push_back(i);

    for(int j=2*i;j<100001;j+=i)is_prime[j]=false;

  }

  int S=pr.size();

  //cout<<S<<endl;

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

  int N;cin>>N;

  std::vector<int> v(N);

  for(int i=0;i<N;i++)cin>>v[i];

  std::vector<int> w(S);

  for(int i=0;i<S;i++)w[i]=pr[i]*pr[i]*pr[i];

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

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

      if(v[i]<w[j])break;

      if(v[i]%w[j]==0)v[i]/=w[j--];

    }

  }

  map<int,int> m;

  for(int i=0;i<N;i++)m[v[i]]++;

  int ans=0;

  for(auto p:m){

    if(p.second<0)continue;

    if(p.first==1)continue;

    int res=1,n=p.first;

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

      if(n<pr[j]*pr[j])break;

      if(n%pr[j])continue;

      if(n%(pr[j]*pr[j])==0){res*=pr[j];n/=pr[j]*pr[j];}

      else {res*=pr[j]*pr[j];n/=pr[j];}

    }

    res*=n*n;

    //cout<<"P"<<p.first<<" "<<res<<endl;

    if(m.count(res)){

      ans+=max(p.second,m[res]);

      m[res]=-1;

    }

    else ans+=p.second;

  }

  if(m[1])ans++;

  fin(ans);

}


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

using namespace std;



#define int long long

int prime[2234];

vector<int>vp;





signed main(){

  for(int i=2;i<2234;i++)prime[i]=1;

  for(int i=2;i<2234;i++)

    if(prime[i]){

      vp.push_back(i);

      for(int j=i*i;j<2234;j+=i)prime[j]=0;

    }

  int n;cin>>n;

  vector<int> v(n);

  for(int i=0;i<n;i++)cin>>v[i];

  map<int,int> m;

  int ans=0;

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

    for(int p:vp)while(v[i]%(p*p*p)==0)v[i]/=p*p*p;

    if(v[i]==1)ans|=1;

    else m[v[i]]++;

  }

  for(auto p:m){

    int a=p.first;

    int tui=1;

    for(int q:vp){

      if(a%(q*q)==0){

        tui*=q;

        a/=q*q;

      }

      if(a%q==0){

        tui*=q*q;

        a/=q;

      }

    }

    if(a<1e6)tui*=a*a;

    else{

      int tmp=sqrt(a);

      if(a==tmp*tmp)tui*=tmp;

      else if(a==(tmp-1)*(tmp-1))tui*=tmp-1;

      else if(a==(tmp+1)*(tmp+1))tui*=tmp+1;

      else tui*=0;

    }

    if(!(m.count(tui)&&(m[tui]>p.second||(m[tui]==p.second&&tui>p.first))))ans+=p.second;

  }

  cout<<ans<<endl;

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

using namespace std;

#define V vector

#define vel V<long long>

#define rep(i,n) for(int i=0;i<n;i++)

vel solve(V<vel>& ab, int ex) {

	if (!ex) { return { 1, 0 }; }

	V<V<vel>> qab(2);

	for (vel x : ab) {

		qab[x[1] & 1].push_back({ x[0] / 2,x[1] / 2 });

		if (x[0] & 1) { qab[(x[1] + 1) & 1].push_back({ x[0] / 2,(x[1] + 1) / 2 }); }

	}

	V<vel> c(3, vel(2));

	rep(i, 2) {

		for (vel x : qab[i]) {

			int qc = (2 * x[0] + x[1]) % 3;

			if ((qc+1)%2) { c[i][0] ^= 1; }

			if (qc) { c[i][1] ^= 1; }

		}

	}

	rep(i, 2) {

		if (c[1 - i] == c[2]) {

			vel ans = solve(qab[i], ex - 1);

			ans[0] *= 2; ans[1] *= 2; ans[1] += i;

			return ans;

		}

	}

	for(vel &v:ab) { v[0]++; }

	vel ans = solve(ab, ex); ans[0]--;

	return ans;

}

int main() {

	long long inf = 2e17;

	int n; cin >> n;

	V<vel> ab(n);

	rep(i, n) {

		long long a, b; cin >> a >> b;

		ab[i] = { a + inf,b + inf };

	}

	vel ret = solve(ab, 70);

	cout << ret[0] - inf << " " << ret[1] - inf << "\n";

}

// Faster C++ solution for the same problem (measured speedup: 1.108423267484287x):
#include<iostream>

#include<vector>

using namespace std;

#define int long long

#define V vector

#define vel V<int>

#define rep(i,n) for(int i=0;i<n;i++)

#define mkp make_pair

#define pin pair<int,int>

pin solve(V<pin>& ab, int ex) {

	if (!ex) { return mkp(1,0); }

	V<V<pin>> qab(2);

	for (pin x : ab) {

		qab[x.second & 1].push_back(mkp(x.first / 2,x.second / 2));

		if (x.first & 1) { qab[(x.second + 1) & 1].push_back(mkp(x.first / 2,(x.second + 1) / 2)); }

	}

	V<vel> c(2, vel(2));

	rep(i, 2) {

		for (pin x : qab[i]) {

			int qc = (2 * x.first + x.second) % 3;

			if ((qc+1)%2) { c[i][0] ^= 1; }

			if (qc) { c[i][1] ^= 1; }

		}

	}

	rep(i, 2) {

		if (!c[1 - i][0]&&!c[1-i][1]) {

			pin ans = solve(qab[i], ex - 1);

			ans.first *= 2; ans.second *= 2; ans.second += i;

			return ans;

		}

	}

	for(pin &v:ab) { v.first++; }

	pin ans = solve(ab, ex); ans.first--;

	return ans;

}

signed main() {

	long long inf = 2e17;

	int n; scanf("%lld", &n);

	V<pin> ab(n);

	rep(i, n) {

		long long a, b; scanf("%lld", &a); scanf("%lld", &b);

		ab[i] = { a + inf,b + inf };

	}

	pin ret = solve(ab, 70);

	cout << ret.first - inf << " " << ret.second - inf << "\n";

}