#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
#define forn(a, e) for (i64 a = 0; a < (i64)(e); a++)
#define forr(a, s, e) for (i64 a = s; a < (i64)(e); a++)
#define fore(e, a) for (auto& e : a)

#ifdef LOCAL
#define logv(a) {cerr << #a << " = "; fore(e, a) {cerr << e << " ";} cerr << "\n";}
#define logvp(a) {cerr << #a << " = "; fore(e, a) {cerr << "(" << e.first << ", " << e.second << ") ";} cerr << "\n";}
#define logvv(a) {cerr << #a << " = \n"; fore(r, a) { fore(e, r) {cerr << e << " ";} cerr << "\n";} }
#define logvf(a, field) {cerr << #a"."#field << " = \n"; fore(e, a) { cerr << e.field << " ";} cerr << "\n"; }
#define logvff(a, f1, f2) {cerr << #a".{"#f1 << ", "#f2 << "} = \n"; fore(e, a) { cerr << "(" << e.f1 <<", " << e.f2 << ") ";} cerr << "\n"; }
#define logs(a) cerr << #a << " = " << (a) << "\n";
#define logss(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << "\n";
#define logp(a) cerr << #a << " = " << "(" << a.first << ", " << a.second << ")" << "\n";
#define cond(pred, stmt) if (pred) { stmt }
#else
#define logv(a)
#define logvp(a)
#define logvv(a)
#define logvf(a, field)
#define logvff(a, f1, f2)
#define logs(a)
#define logss(a, b)
#define logp(a)
#define cond(pred, stmt)
#endif

using iip = pair<int, int>;
using llp = pair<i64, i64>;
using ivec = vector<int>;
using llvec = vector<i64>;
using svec = vector<string>;
template<typename T> using vec = vector<T>;

template<typename T, typename Dim>
auto make_vec(T value, Dim dim) { return vector<T>(dim, value); }
template<typename T, typename Dim1, typename... Dim>
auto make_vec(T value, Dim1 dim1, Dim... dims) { return make_vec(make_vec(value, dims...), dim1); }

template<typename T>
bool uax(T& v, const T& newv) { if (v < newv) { v = newv; return true; } else return false; }
template<typename T>
bool uin(T& v, const T& newv) { if (v > newv) { v = newv; return true; } else return false; }

template<typename T>
istream& operator>>(istream& is, vector<T>& c) { for (auto& e : c) is >> e; return is; }
template<typename T, size_t N>
istream& operator>>(istream& is, array<T, N>& c) { for (auto& e : c) is >> e; return is; }

template<typename ...T>
istream& read(T&... args) { return (cin >> ... >> args); }

static mt19937 rande(123123);
template<typename T>
T rand_int(T from, T to) { uniform_int_distribution<T> distr(from, to); return distr(rande); }

const i64 INF = 1e18;
const i64 M = 1e9 + 7;
const int MXB = 20;
using bin = bitset<MXB + 1>;

i64 isqrt(i64 a) {
    __int128_t l = 0;
    __int128_t r = a;
    while (r - l > 1) {
        __int128_t m = (r + l) / 2;
        if (m * m > a) {
            r = m;
        } else {
            l = m;
        }
    }
    return l;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    rande.seed(chrono::steady_clock::now().time_since_epoch().count());

    int n;
    while (read(n)) {
        llvec a(n);
        read(a);

        i64 mxa = 0;
        fore(ai, a) {
            uax(mxa, ai);
        }

        llvec sp;
        for (i64 i = 2; i * i * i <= mxa; i++) {
            i64 c = 0;
            for (i64 j = 1; j * j <= i; j++) {
                if (i % j == 0) {
                    if (j * j == i) {
                        c++;
                    } else {
                        c += 2;
                    }
                }
            }
            if (c == 2) {
                sp.push_back(i);
            }
        }
        // logs(mxa);
        // logv(sp);
        vec<vec<llp>> fs(n);
        map<i64, i64> cc;
        map<i64, i64> na;
        forn(i, n) {
            i64 an = 1;
            fore(p, sp) {
                llp cp{p, 0};
                while (a[i] % p == 0) {
                    a[i] /= p;
                    cp.second++;
                }
                cp.second %= 3;
                if (cp.second != 0) {
                    fs[i].push_back(cp);
                }
                forn(j, cp.second) {
                    an *= cp.first;
                }
            }
            if (a[i] != 1) {
                i64 sq = isqrt(a[i]);
                an *= a[i];
                if (sq * sq == a[i]) {
                    fs[i].emplace_back(sq, 2);
                } else {
                    fs[i].emplace_back(a[i], 1);
                }
            }
            cc[an]++;
            i64 aa = 1;
            for (auto [p, c] : fs[i]) {
                if (c == 2) {
                    aa *= p;
                } else {
                    aa *= p * p;
                }
            }
            na[an] = aa;
        }
        i64 ans = 0;
        set<i64> gs;
        fore(kv, cc) {
            auto nc = na.count(kv.first) && cc.count(na[kv.first]) ? cc[na[kv.first]] : 0;
            if (kv.first == 1) {
                ans += 1;
            } else {
                if (kv.second > nc) {
                    gs.insert(kv.first);
                } else if (kv.second == nc) {
                    gs.insert(min(kv.first, na[kv.first]));
                } else {
                    gs.insert(na[kv.first]);
                }
            }
        }
        // logvp(cc);
        // logvp(na);
        // logv(gs);
        fore(g, gs) {
            ans += cc[g];
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 31188