// Original C++ solution (slower):
#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;



typedef long long ll;

const int MAXN = 1e5 + 10;

ll n, a[MAXN], b[MAXN], C;

vector<ll> p, Mat[MAXN];

bool isp[MAXN], se[MAXN];

int cnt[MAXN], sh, shr;



ll getmsk(ll t) {

	for (int i = 0; p[i] * p[i] * p[i] <= t; i++) {

		ll r = p[i] * p[i] * p[i];

		while (t % r == 0)

			t /= r;

	}

	return t;

}

ll rmsk(ll t) {

	ll m = 1;

	for (int i = 0; p[i] * p[i] <= t; i++) {

		if (t % (p[i] * p[i]) == 0)

			m *= p[i], t /= p[i] * p[i];

		else if (t % p[i] == 0)

			m *= p[i] * p[i], t /= p[i];

	}

	if (t != 1)

		m *= t * t;

	return m;

}



void dfs(int v, bool cl) {

	se[v] = 1;

	sh += cnt[v];

	if (cl)

		shr += cnt[v];

	for (int i = 0; i < Mat[v].size(); i++)

		if (!se[Mat[v][i]])

			dfs(Mat[v][i], !cl);

}



int main() {

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

		if (!isp[i]) {

			p.push_back(i);

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

				isp[j] = 1;

		}

	cin >> n;

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

		cin >> a[i], a[i] = getmsk(a[i]);

	sort(a, a + n);

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

		b[C] = a[i];

		while (i < n && a[i] == b[C])

			cnt[C]++, i++;

		C++;

	}

	for (int i = (a[0] == 1); i < C; i++) {

		ll t = rmsk(b[i]);

		int f = lower_bound(b, b + C, t) - b;

		if (f == C || b[f] != t)

			continue;

		Mat[i].push_back(f);

	}

	int ans = 0;

	for (int i = (b[0] == 1); i < C; i++)

		if (!se[i]) {

			sh = shr = 0;

			dfs(i, 0);

			ans += max(shr, sh - shr);

		}

	ans += b[0] == 1;

	cout << ans;

}

// Optimized solution to the same problem (faster):
#include <map>

#include <cmath>

#include <cstdio>

#include <iostream>



typedef long long LL;

#define int LL



const int MAXN = 1e5, MAXFAC = 2155;

const LL MAXV = 1e10;

int n, pn, pr[MAXFAC + 5], siz[MAXN + 5], rev[MAXN + 5];

LL val[MAXN + 5];

bool vis[MAXFAC + 5];

std::map<LL, int> buc;



inline LL rint () {

	LL x = 0; char s = getchar ();

	for ( ; s < '0' || '9' < s; s = getchar () );

	for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );

	return x;

}



inline void sieve ( const int n ) {

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

		if ( ! vis[i] ) pr[++ pn] = i;

		for ( int j = 1; j <= pn && i * pr[j] <= n; ++ j ) {

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

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

		}

	}

}



inline bool issqr ( const LL x ) {

	LL t = pow ( x, 1.0 / 3 );

	return t * t * t == x || ( t + 1 ) * ( t + 1 ) * ( t + 1 ) == x;

}



signed main () {

	n = rint (), sieve ( MAXFAC );

	int ans = 0;

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

		LL a = rint ();

		if ( issqr ( a ) ) { ans = 1; continue; }

		LL cur = 1, mtc = 1;

		for ( int j = 1; j <= pn && pr[j] <= a; ++ j ) {

			int cnt = 0;

			for ( ; ! ( a % pr[j] ); a /= pr[j], ++ cnt );

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

			cur *= pr[j], mtc *= pr[j];

			if ( cnt == 1 ) mtc *= pr[j];

			else cur *= pr[j];

			if ( mtc > MAXV ) mtc = 0;

		}

		LL sqt = sqrt ( a );

		cur *= a;

		if ( sqt * sqt == a || ( sqt + 1 ) * ( sqt + 1 ) == a ) mtc *= sqt;

		else {

			mtc *= a;

			if ( mtc > MAXV ) mtc = 0;

			mtc *= a;

		}

		if ( mtc > MAXV ) mtc = 0;

		if ( ! buc.count ( cur ) ) siz[buc[cur] = i] = 1, rev[i] = mtc;

		else ++ siz[buc[cur]];

		val[i] = cur;

	}

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

		if ( ! siz[i] ) continue;

		if ( ! buc.count ( rev[i] ) ) {

			ans += siz[i], siz[i] = 0;

		} else {

			ans += std::max ( siz[i], siz[buc[rev[i]]] );

			siz[i] = siz[buc[rev[i]]] = 0;

		}

	}

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

	return 0;

}

// Fastest known solution for this problem: