#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <queue>
#include <math.h>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <bitset>
#include <list>
#include <ctype.h>
#include <cassert>
#include <stack>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <functional>
#include <ctime>
#include <limits>
#include <tuple>
#include <complex>

using namespace std;

#define snd second
#define fst first
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define left _left
#define right _right

const ld pi = acos(-1.0l);

template<typename T>
T abs(T x) {
    return x > 0 ? x : -x;
}

template<typename T>
T sqr(T x) {
    return x * x;
}

template<typename T>
void chmin(T &x, T y) {
    x = min(x, y);
}

template<typename T>
void chmax(T &x, T y) {
    x = max(x, y);
}

template<typename U, typename V>
ostream &operator<<(ostream &s, const pair<U, V> &x) {
    s << "(" << x.fst << ", " << x.snd << ")";
    return s;
}

template<typename U>
ostream &operator<<(ostream &s, const vector<U> &x) {
    s << "[";
    bool was = false;
    for (auto it : x) {
        if (was) {
            s << ", ";
        }
        was = true;
        s << it;
    }
    s << "]";
    return s;
}

template<typename U>
ostream &operator<<(ostream &s, const set<U> &x) {
    s << "{";
    bool was = false;
    for (auto it : x) {
        if (was) {
            s << ", ";
        }
        was = true;
        s << it;
    }
    s << "}";
    return s;
}

template<int sz>
ostream operator<<(ostream &s, const bitset<sz> &x) {
    for (int i = 0; i < sz; i++) {
        s << x[i];
    }
    return s;
}


//-----------------------------------------------------------------------------

const int ub = 2222;

int main() {
    srand(time(NULL));

    retry:
#ifdef LOCAL
    //gen();
    freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    int n;
    cin >> n;
    map<vector<pair<ll,int>>, int> a;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        ll xo = x;

        vector<pair<ll,int>> c;
        for (int j = 2; j < ub; j++) {
            int f = 0;
            if (x % j == 0) {
                while (x % j == 0) {
                    f++;
                    x /= j;
                }
                f %= 3;
                ll g = (3 - f) % 3;
                if (f) {
                    c.pb(mp(j, f));
                }
            }
        }

        ll lo = 0, hi = 1e6;
        while (hi - lo > 1) {
            ll mid = (lo + hi) >> 1;
            if (sqr(mid) <= x) {
                lo = mid;
            } else {
                hi = mid;
            }
        }



        if (x > 1 && sqr(lo) == x) {
            c.pb(mp(lo, 2));
        } else if (x > 1) {
            c.pb(mp(x, 1));
        }

        sort(c.begin(), c.end());

        a[c]++;
    }


    set<vector<pair<ll, int>>> was;
    for (auto kv : a) {
        if (kv.fst == vector<pair<ll, int>>()) {
            ans++;
            continue;
        }
        if (was.count(kv.fst)) {
            continue;
        }

        vector<pair<ll, int>> d = kv.fst;
        for (auto &x : d) {
            x.snd = 3 - x.snd;
        }

        if (a.count(d)) {
            ans += max(a[d], a[kv.fst]);
            was.insert(d);
        } else {
            ans += kv.snd;
        }
    }





    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 14592