// 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.209203047199986x):
#include <map>

#include <cmath>

#include <cstdio>



typedef long long LL;



const int MAXN = 1e5 + 5;



template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}

	x *= f;

}



template<typename _T>

void write( _T x )

{

	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}



template<typename _T>

_T MAX( const _T a, const _T b )

{

	return a > b ? a : b;

}



std :: map<LL, int> mp;



LL a[MAXN], oppo[MAXN];

LL pw2[MAXN], pw3[MAXN];



int prime[MAXN], pn;

int N;



bool isPrime[MAXN];



void EulerSieve( const int siz )

{

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

	{

		if( ! isPrime[i] ) prime[++ pn] = i;

		for( int j = 1 ; j <= pn && 1ll * i * prime[j] <= siz ; j ++ )

		{

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

			if( ! ( i % prime[j] ) ) break;

		}

	}

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

		pw2[i] = 1ll * prime[i] * prime[i], pw3[i] = 1ll * pw2[i] * prime[i];

}



int main()

{

	bool flg = false;

	read( N ); EulerSieve( 3000 );

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

	{

		read( a[i] );

		for( int k = 1 ; k <= pn && pw3[k] <= a[i] ; k ++ )

			while( ! ( a[i] % pw3[k] ) )

				a[i] /= pw3[k];

		if( a[i] == 1 ) flg = true, mp[a[i]] = -1;

		else

		{

			mp[a[i]] ++;

			LL tmp = a[i];

			int tot = 0, indx; LL rest = 1;

			for( int k = 1 ; k <= pn && prime[k] <= tmp ; k ++ )

				if( ! ( tmp % prime[k] ))

				{

					tot ++, indx = 0;

					while( ! ( tmp % prime[k] ) )

						indx ++, tmp /= prime[k];

					if( indx & 1 ) rest = 1ll * rest * pw2[k];

					else rest = 1ll * rest * prime[k];

				}

			int t = sqrt( tmp );

			if( 1ll * t * t == tmp ) oppo[i] = 1ll * t * rest;

			else oppo[i] = ( tmp <= 1e5 ? rest * tmp * tmp : 0 );

		}

	}

	int ans = 0;

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

		if( ~ mp[a[i]] )

			ans += MAX( mp[a[i]], mp[oppo[i]] ),

			mp[a[i]] = mp[oppo[i]] = -1;

	write( ans + flg ), putchar( '\n' );

	return 0;

}