#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    map<int64_t, int> s;
    for (int i = 0; i < n; ++i) {
        int64_t x;
        // x = 1LL * rand() * rand() % 10000000000 + 1;
        scanf("%lld", &x);
        s[x]++;
    }

    auto fmul = [&](int64_t a, int64_t b, int64_t p) {
        return (int64_t)((__int128)a * b % p);
        // a %= p;
        // b %= p;
        // int64_t res = 0;
        // while (b > 0) {
            // if (b & 1) (res += a) >= p ? res -= p : 0;
            // (a += a) >= p ? a -= p : 0;
            // b >>= 1;
        // }
        // return res;
    };

    auto fpow = [&](int64_t a, int64_t b, int64_t p) {
        int64_t res = 1;
        while (b > 0) {
            if (b & 1) res = fmul(res, a, p);
            a = fmul(a, a, p);
            b >>= 1;
        }
        return res;
    };

    auto Check = [&](int64_t a, int64_t u, int64_t n, int t) {
        a = fpow(a, u, n);
        if (a == 0 || a == 1 || a == n - 1) return true;
        for (int i = 0; i < t; ++i) {
            a = fmul(a, a, n);
            if (a == 1) return false;
            if (a == n - 1) return true;
        }
        return false;
    };

    auto IsPrime = [&](int64_t n) {
        constexpr array<int64_t, 4> kChk = {2, 13, 23, 1662803};
        if (n < 2) return false;
        if (n % 2 == 0) return n == 2;
        int64_t u = n - 1;
        int t = 0;
        for (; !(u & 1); u >>= 1, t++);
        for (auto v : kChk) {
            if (!Check(v, u, n, t)) return false;
        }
        return true;
    };

    auto Factorize = [&](int64_t x) {
        vector<int64_t> pr;
        function<void(int64_t)> PollardRho = [&](int64_t n) {
            if (n == 1) return;
            if (IsPrime(n)) {
                pr.push_back(n);
                return;
            }
            if (n % 2 == 0) {
                pr.push_back(2);
                PollardRho(n / 2);
                return;
            }
            int64_t x = 2, y = 2, d = 1, p = 1;

            auto f = [&](int64_t x, int64_t n, int p) {
                return (fmul(x, x, n) + p) % n;
            };

            while (true) {
                if (d != n && d != 1) {
                    PollardRho(d);
                    PollardRho(n / d);
                    break;
                }
                if (d == n) p++;
                x = f(x, n, p);
                y = f(f(y, n, p), n, p);
                d = __gcd(abs(x - y), n);
            }
        };

        PollardRho(x);
        sort(pr.begin(), pr.end());
        vector<pair<int64_t, int>> res;
        for (int i = 0, j = 0; i < pr.size(); i = j) {
            for (; j < pr.size() && pr[j] == pr[i]; ++j);
            if ((j - i) % 3) res.emplace_back(pr[i], (j - i) % 3);
        }
        return res;
    };

    int ans = 0;
    map<vector<pair<int64_t, int>>, int> mp;
    for (auto it : s) {
        auto f = Factorize(it.first);
        if (f.empty()) ans = 1;
        else mp[f] += it.second;
    }

    set<vector<pair<int64_t, int>>> seen;
    for (auto it : mp) {
        if (seen.count(it.first)) continue;
        vector<pair<int64_t, int>> inv(it.first.begin(), it.first.end());
        for (auto &k : inv) k.second = 3 - k.second;
        if (mp.find(inv) == mp.end()) {
            ans += it.second;
        } else {
            ans += max(it.second, mp[inv]);
            seen.insert(it.first);
            seen.insert(inv);
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 20992