#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <cmath>
using namespace std;

const int Times = 10;
const int N = 100005;

typedef long long LL;

struct FastIO {
	static const int S = 1310720;
	int wpos; char wbuf[S];
	FastIO() : wpos(0) {}
	inline int xchar() {
		static char buf[S];
		static int len = 0, pos = 0;
		if (pos == len)
			pos = 0, len = fread(buf, 1, S, stdin);
		if (pos == len) return -1;
		return buf[pos ++];
	}
	inline int xuint() {
		int c = xchar(), x = 0;
		while (c <= 32 && ~c) c = xchar();
		if (c == -1) return -1;
		for (;'0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
		return x;
	}
	inline long long xull() {
		int c = xchar();
		long long x = 0;
		while (c <= 32 && ~c) c = xchar();
		if (c == -1) return -1;
		for (;'0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
		return x;
	}
	inline int xint() {
		int s = 1, c = xchar(), x = 0;
		while (c <= 32) c = xchar();
		if (c == '-') s = -1, c = xchar();
		for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
		return x * s;
	}
	inline void xstring(char *s) {
		int c = xchar();
		while (c <= 32) c = xchar();
		for(; c > 32; c = xchar()) *s++ = c;
		*s = 0;
	}
	inline void wchar(int x) {
		if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
		wbuf[wpos ++] = x;
	}
	inline void wint(int x) {
		if (x < 0) wchar('-'), x = -x;

		char s[24];
		int n = 0;
		while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
		while (n--) wchar(s[n]);
	}
	inline void wstring(const char *s) {
		while (*s) wchar(*s++);
	}
	~FastIO() {
		if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
	}
} io;

LL cnt;
LL fac[N], num[N];
int pri[N], vis[N], pn;

LL isq(LL n) {
	LL m = sqrt(n + 0.5);
	if (m * m == n) return m;
	return -1;
}

bool get(LL n) {
	cnt = 0;
	if (n == 1) return false;
	for (int i = 0; i < pn; i++) {
		if (pri[i] > 3000) break;
		if (n % pri[i] == 0) {
			fac[cnt] = pri[i];
			num[cnt] = 0;
			while (n % pri[i] == 0) {
				n /= pri[i];
				num[cnt]++;
				if (num[cnt] == 3) num[cnt] = 0;
			}
			if (num[cnt]) cnt++;
		}
	}
	if (n == 1) return false;
	LL sq = isq(n);
	if (n != 1 && sq != -1) {
		fac[cnt] = sq;
		num[cnt++] = 2;
		return false;
	}
	if (n <= 100000LL && vis[n] == 0) {
		fac[cnt] = n;
		num[cnt++] = 1;
		return false;
	}
	return true;
}

#define fi first
#define se second
#define mp(a,b) make_pair(a,b)
typedef pair<long long, int> pii;

int n;
LL a[N];

struct Node {
	vector<pii> p;
	Node() {p.clear();}
	bool operator < (const Node& c) const {
		if (p.size() != c.p.size()) return p.size() < c.p.size();
		for (int i = 0; i < p.size(); i++)
			if (p[i] < c.p[i]) return true;
		return false;
	}

	long long v1, v2;

	void gao() {
		v1 = 1, v2 = 1;
		for (int i = 0; i < p.size(); i++) {
			pii tmp = p[i];
			for (int j = 0; j < 3 - tmp.se; j++) v2 *= tmp.fi;
			for (int j = 0; j < tmp.se; j++) v1 *= tmp.fi;
		}
	}

} nd[N];

map<long long, int> sb;

int cc[N];

int id[N], cao[N];

bool cmp(int i, int j) {
	return cc[i] < cc[j];
}

int main() {
	vis[0] = vis[1] = 1;
	for (int i = 2; i < N; i++) {
		if (vis[i]) continue;
		pri[pn++] = i;
		if (1LL * i * i >= 1LL * N) continue;
		for (int j = i * i; j < N; j += i)
			vis[j] = 1;
	}
	n = io.xuint();
	memset(cc, 0, sizeof(cc));
	for (int i = 1; i <= n; i++) {
		a[i] = io.xull();
		id[i] = i;
	}
	for (int i = 1; i <= n; i++) {
		if (get(a[i])) {
			cao[i] = 1;
			continue;
		}
		for (int j = 0; j < cnt; j++)
			nd[i].p.push_back(mp(fac[j], num[j]));
		nd[i].gao();
		sb[nd[i].v1]++;
	}
	for (int i = 1; i <= n; i++) {
		if (cao[i]) continue;
		if (nd[i].p.size() == 0) {
			cc[i] = sb[nd[i].v2];
			cc[i]--;
			continue;
		}
		cc[i] = sb[nd[i].v2];
	}
	sort(id + 1, id + 1 + n, cmp);
	sb.clear();
	int ans = 0;
	for (int ii = 1; ii <= n; ii++) {
		int i = id[ii];
		if (cao[i]) {
			ans++;
			continue;
		}
		if (sb.count(nd[i].v2)) continue;
		sb[nd[i].v1]++;
		ans++;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 23168