#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
//#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define INFST (0x7f7f7f7f)
#define INFLLST (0x7f7f7f7f7f7f7f7fll)
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
typedef complex<ld> base;
const ld EPS = (ld)1e-7;
const ld PI = acos(0) * 2;
bool isZero(const ld& x) { return abs(x) <= EPS; }
int sign(const ld& x) { return isZero(x) ? 0 : (0 < x ? 1 : -1); }
ll gcd(ll a, ll b) { for(;b;a%=b,swap(a,b)){} return abs(a); }
pll operator + (const pll& a, const pll& b) { return pll(a.first+b.first, a.second+b.second); }
pll operator - (const pll& a, const pll& b) { return pll(a.first-b.first, a.second-b.second); }
pll operator * (const pll& a, const ll& b) { return pll(a.first*b, a.second*b); }
ll operator * (const pll& a, const pll& b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll& a, const pll& b, const pll& c) { return a*b + b*c + c*a; }
int rd(int s, int e) { return rand()%(e-s+1) + s; }
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
void fg(vector<pii> G[], int a, int b, int c) { G[a].pb({b, c}); G[b].pb({a, c}); }

ll mul(ll a, ll b, const ll &mod) {
	ll ret = 0;
	for(a %= mod, b %= mod; a; a >>= 1) {
		if(a&1) ret = (ret + b) % mod;
		b = (b<<1) % mod;
	}
	return ret;
}
// a^b % MOD
ll mypow(ll a, ll b, const ll& mod) {
	ll ret = 1; for(a %= mod; b; b >>= 1) {
		if(b&1) ret = mul(ret, a, mod);
		a = mul(a, a, mod);
	}
	return ret;
}

bool mrtest(ll x, ll a) {
	if(!(x%a)) return false;
	for(ll d = x-1, t;; d >>= 1) {
		t = mypow(a, d, x);
		if(d&1) return ((1 != t) && (x-1 != t));
		if(x-1 == t) return false;
	}
	return false;
}
const int mrV[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

bool mrrun(ll x, const bool iscut = false) {
	if(2 == x) return true;
	if(x < 2 || !(x&1)) return false;
	if(iscut && x < 10000) {
		for(int i = 3; i*i <= x; i += 2)
			if(!(x%i)) return false;
		return true;
	}
	for(int v : mrV) {
		if(x == v) return true;
		if(40 < x && mrtest(x, v)) return false;
	}
	return 40 < x;
}

ll f(ll x, ll n, ll c) {
	return (mul(x, x, n) + c) % n;
}
void g(vector<ll> &ret, ll x) {
	if(1 == x) return;
	if(mrrun(x)) {
		ret.pb(x); return;
	}
	for(ll a, b, c, t;;) {
		a = b = rd(2, x-1);
		c = rd(1, 20);
		do {
			a = f(a, x, c);
			b = f(f(b, x, c), x, c);
		} while(1 == (t = gcd(abs(a-b), x)));
		if(a == b) continue;
		g(ret, t); g(ret, x/t);
		return;
	}
}

void facrun(vector<ll> &ret, ll x) {
	clv(ret); if(x < 2) return;
	for(; !(x&1); x >>= 1) ret.pb(2);
	g(ret, x);
	sorv(ret);
}


const int MAXN = 100005;
const ll MAXX = 10000000005ll;

unordered_map<ll, int> MP;
vector<pll> VA;
vector<pair<pll, int>> VB;

ll A[MAXN];

int Ans;
int N;

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) {
		cin >> A[i];
		if(1 == A[i]) {
			VA.eb(1, 1);
			continue;
		}

		vector<ll> FV;
		//facrun(FV, A[i]);

		{
			ll n = A[i];
			for(; !(n&1); n >>= 1) FV.eb(2);
			for(int i = 3; i < 2222; i += 2)
				for(; 0 == n%i; n /= i) FV.eb(i);
			if(1 < n) FV.eb(n);
		}
		vector<pair<ll, int>> V;
		for(ll v : FV) {
			if(V.empty() || V.back().first != v) {
				V.eb(v, 1);
			} else {
				V.back().second++;
			}
		}

		for(auto &v : V) v.second %= 3;

		ll n = 1; lll mm = 1;
		for(auto &v : V) {
			if(!v.second) continue;
			for(int i = 0; i < v.second; i++)
				n *= v.first;
			for(int i = 0; i < 3-v.second; i++)
				mm *= v.first;
		}

		if(MAXX < mm) mm = MAXX;

		VA.eb(n, mm);

		//fprintf(stderr, "TEST %d\n", i);
	}

	sorv(VA);

	{
		for(int i = 0; i < sz(VA);) {
			if(sz(VA) <= i+1 || VA[i] != VA[i+1]) {
				VB.eb(VA[i], 1);
				i++;
				continue;
			}
			VB.eb(VA[i], 0);
			for(ll c = VA[i].first; i < sz(VA) && VA[i].first == c; VB.back().second++, i++);
		}
	}

	for(auto &e : VB) {
		MP[e.first.first] = e.second;
	}

	for(auto &e : VB) {
		if(!MP[e.first.first]) continue;
		if(e.first.first == 1) {
			Ans++;
			MP[1] = 0;
			continue;
		}
		if(MAXX == e.first.second) {
			Ans += MP[e.first.first];
			MP[e.first.first] = 0;
			continue;
		}
		Ans += max(MP[e.first.first], MP[e.first.second]);
		MP[e.first.first] = MP[e.first.second] = 0;
	}

	cout << Ans << endl;
	return 0;
}

Measured memory_bytes: 12652