#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<pii, int> para;
const int inf = 1e9 + 7;
const int maxN = 5e6 + 5;

int n;
map<ll, int> freq;
int ans;

bool isSquare(ll x, ll y) {
	return x * x == y;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		ll a;
		cin >> a;
		freq[a]++;
	}

	// wykladniki > 3
	for(ll i = 2; i <= (ll)1e6; i++) {
		ll x = i * i * i;
		long double d = x;
		// potrzebujemy long double bo ll moze sie przekrecic :P
		while (d <= 1e18) {
			if (freq.find(x) != freq.end()) {
				ans += freq[x];
				freq.erase(x);
			}
			d *= (long double)i;
			x *= i;
		}
	}

	// wykladnik = 2
	for (auto k: freq) {
		ll p = (ll)sqrt(k.st);
		if (isSquare(p, k.st) || isSquare(p + 1, k.st)) {
			ans += k.nd;
		}
	}
	cout << ans << endl;
	return 0;
}