#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
//#pragma warning(disable : 4996)

#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64
#endif

#include <limits.h>
#include <math.h>
#include <time.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m - 1; i >= n; --i)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v, n) reverse(v, v + n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout << (x) << '\n'
#define pe(x) cout << (x) << " "
#define DEBUG(x) cout << #x << ": " << x << endl
#define lb(v, n) lower_bound(v.begin(), v.end(), (n))
#define ub(v, n) upper_bound(v.begin(), v.end(), (n))
//#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i, v.size()) cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template <typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template <typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9 + 7;
constexpr int MAX = 500050;
const double pi = acos(-1);
constexpr double EPS = 1e-8;
constexpr ll LINF = 1e18 + 1;
constexpr int INF = 1e9 + 1;

//ミラーラビン素数判定法とポラード・ロー法のコードは http://quiz.fuqinho.net/blog/2012/06/12/poj-2429-gcd-and-lcm-inverse/ より

// return (a * b) % m
ll mod_mult(ll a, ll b, ll m) {
	ll res = 0;
	ll exp = a % m;
	while (b) {
		if (b & 1) {
			res += exp;
			if (res > m) res -= m;
		}
		exp <<= 1;
		if (exp > m) exp -= m;
		b >>= 1;
	}
	return res;
}

// return (a ^ b) % m
ll mod_exp(ll a, ll b, ll m) {
	ll res = 1;
	ll exp = a % m;
	while (b) {
		if (b & 1) res = mod_mult(res, exp, m);
		exp = mod_mult(exp, exp, m);
		b >>= 1;
	}
	return res;
}

// ミラー-ラビン素数判定法
bool miller_rabin(ll n, ll times) {
	if (n < 2) return false;
	if (n == 2) return true;
	if (!(n & 1)) return false;

	ll q = n - 1;
	int k = 0;
	while (q % 2 == 0) {
		k++;
		q >>= 1;
	}
	// n - 1 = 2^k * q (qは奇素数)
	// nが素数であれば、下記のいずれかを満たす
	// (i) a^q ≡ 1 (mod n)
	// (ii) a^q, a^2q,..., a^(k-1)q のどれかがnを法として-1
	//
	// なので、逆に(i)(ii)いずれも満たしていない時は合成数と判定できる
	//
	for (int i = 0; i < times; i++) {
		ll a = rand() % (n - 1) + 1; // 1,..,n-1からランダムに値を選ぶ
		ll x = mod_exp(a, q, n);
		// (i)をチェック
		if (x == 1) continue;
		// (ii)をチェック
		bool found = false;
		for (int j = 0; j < k; j++) {
			if (x == n - 1) {
				found = true;
				break;
			}
			x = mod_mult(x, x, n);
		}
		if (found) continue;

		return false;
	}
	return true;
}

ll get_gcd(ll n, ll m) {
	if (n < m) swap(n, m);
	while (m) {
		swap(n, m);
		m %= n;
	}
	return n;
}

// ポラード・ロー素因数分解法
ll pollard_rho(ll n, int c) {
	ll x = 2;
	ll y = 2;
	ll d = 1;
	while (d == 1) {
		x = mod_mult(x, x, n) + c;
		y = mod_mult(y, y, n) + c;
		y = mod_mult(y, y, n) + c;
		d = get_gcd((x - y >= 0 ? x - y : y - x), n);
	}
	if (d == n) return pollard_rho(n, c + 1);
	return d;
}

const int MAX_PRIME = 100;
vector<int> primes;
vector<bool> is_prime;

// 小さい素数(MAX_PRIMEまで)は先に用意しとく
void init_primes() {
	is_prime = vector<bool>(MAX_PRIME + 1, true);
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= MAX_PRIME; i++) {
		if (is_prime[i]) {
			primes.push_back(i);
			for (int j = i * 2; j <= MAX_PRIME; j += i) {
				is_prime[j] = false;
			}
		}
	}
}

// 素数かどうか判定。大きければミラーラビンを使う
bool isPrime(ll n) {
	if (n <= MAX_PRIME) return is_prime[n];
	else return miller_rabin(n, 7);
}

// 素因数分解する。小さい数は用意した素数で試し割り、大きければポラード・ロー
void factorize(ll n, unordered_map<ll, int>& factors) {
	if (isPrime(n)) {
		factors[n]++;
	}
	else {
		for (int i = 0; i < primes.size(); i++) {
			int p = primes[i];
			while (n % p == 0) {
				factors[p]++;
				n /= p;
			}
		}
		if (n != 1) {
			if (isPrime(n)) {
				factors[n]++;
			}
			else {
				ll d = pollard_rho(n, 1);
				factorize(d, factors);
				factorize(n / d, factors);
			}
		}
	}
}



void solve() {
	init_primes();
	int N; cin >> N;
	vector<ll>S(N);
	REP(i, N)cin >> S[i];
	map<ll, int>cnt;
	vector<unordered_map<ll, int>>facs(N);
	REP(i, N) {
		//DEBUG(S[i]);
		if (S[i] != 1) {
			factorize(S[i], facs[i]);
		}
		//print("factorize done");
		for (auto &x : facs[i]) {
			x.second %= 3;
		}
		S[i] = 1;
		//cerr << facs[i].size() << endl;
		for (auto x : facs[i]) {
			ll t = 1;
			//assert(x.second < 3);
			REP(_, x.second)t *= x.first;
			S[i] *= t;
		}
		cnt[S[i]]++;
	}

	unordered_map<ll, bool>done;
	int ans = 0;
	REP(i, N) {
		if (S[i] == 1) {
			if (!done[1])ans++;
			done[1] = true;
		}
		else {
			if (done[S[i]])continue;
			done[S[i]] = true;
			ll pa = 1;
			for (auto x : facs[i]) {
				if (x.second == 0)continue;
				ll t = 1;
				REP(_, 3 - x.second)t *= x.first;
				pa *= t;
			}
			if (done[pa])continue;
			ans += max(cnt[S[i]], cnt[pa]);
			done[pa] = true;
		}
	}
	print(ans);
}


signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q;
	//cin >> q;
	//while (q--)
	solve();
}


Measured memory_bytes: 45348