#include <bits/stdc++.h>

#define ford(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define for1(i, n) for(int i = 1; i <= (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define clr(x) memset((x), 0, sizeof((x)));
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long i64;
typedef unsigned long long ull;

template<class T>
bool remin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool remax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int nxt() {
    int x;
    scanf("%d", &x);
    return x;
}

ll gcd(ll a, ll b) {
    a = abs(a);
    b = abs(b);
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

typedef ld ptdata;

struct pt {
    ptdata x, y;

    pt() {}

    pt(ptdata x, ptdata y) : x(x), y(y) {}

    inline pt operator-(const pt &r) const {
        return pt(x - r.x, y - r.y);
    }

    inline pt operator+(const pt &r) const {
        return pt(x + r.x, y + r.y);
    }

    inline pt operator*(const ptdata &r) const {
        return pt(x * r, y * r);
    }

    inline ptdata sqlen() const {
        return abs(x * x + y * y);
    }

    inline ld len() const {
        return sqrt(sqlen());
    }

    inline bool operator<(const pt &r) const {
        if (x != r.x) return x < r.x;
        return y < r.y;
    }

    inline bool operator==(const pt &r) const {
        return x == r.x && y == r.y;
    }
};

ostream &operator<<(ostream &os, const pt &p) {
    return os << "(" << p.x << "," << p.y << ")";
}

inline ptdata cross(const pt &l, const pt &r) {
    return l.x * r.y - l.y * r.x;
}

inline ptdata dot(const pt &l, const pt &r) {
    return l.x * r.x + l.y * r.y;
}


ll pwmod(ll a, ll n, ll mod) {
    ll ret = 1;
    while (n) {
        if (n & 1) ret = ret * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ret;
}

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

const ll RR = 2200;
vector<ll> cubes;

bool isCube(ll v) {
    ll l = 0, r = (int)cubes.size();
    while (l < r) {
        ll m = (l + r) >> 1;
        ll m3 = cubes[m];
        if (m3 >= v) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return cubes[l] == v;
}

ll sq(ll v) {
    ll t = (ll)sqrt(v);
    for (ll j = t - 1; j <= t + 1; ++j) {
        if (j * j == v) {
            return j;
        }
    }
    return -1;
}

inline void solve() {
    for (ll j = 1; j <= RR; ++j) {
        cubes.push_back(j * j * j);
    }
    int n;
    cin >> n;
    vector<ll> a(n);
    forn(i, n) {
        cin >> a[i];
    }
    vector<ll> b;
    int cnt_cubes = 0;

    forn(i, n) {
        bool ok = isCube(a[i]);
        if (ok) {
            ++cnt_cubes;
        } else {
            b.push_back(a[i]);
        }
    }
    int ans = 0;
    if (cnt_cubes) ++ans;
    a.swap(b);
    n = (int)a.size();
    b.clear();
    sort(all(a));

    vector<vector<int> > g(n);
    map<vector<pair<ll, int> >, int> mcnt;

    forn(i, n) {
        ll v = a[i];
        int ps = lower_bound(all(cubes), v) - cubes.begin();
        for (int j = ps; j > 0; --j) {
            if (v % cubes[j] == 0) {
                v /= cubes[j];
                break;
            }
        }
        a[i] = v;
    }
    vector<ll> pr;
    vector<char> u(100 * 100, 0);
    for (int i = 2; i < 100 * 100; ++i) {
        if (u[i]) continue;
        pr.push_back(i);
        for (int j = i + i; j < 100 * 100; j += i) {
            u[j] = 1;
        }
    }

    forn(j, n) {
        ll v = a[j];
        vector<pair<ll, int> > res;
        for (int i = 0; i < pr.size() && pr[i] < RR; ++i) {
            PII pa = PII(pr[i], 0);
            while (v % pr[i] == 0) {
                v /= pr[i];
                pa.second++;
            }
            if (pa.second) {
                res.push_back(pa);
            }
        }
        if (v > 1) {
            ll ss = sq(v);
            if (ss == -1) {
                res.push_back(mp(v, 1));
            } else {
                res.push_back(mp(ss, 2));
            }
        }
        mcnt[res]++;
    }
    ll ans2 = 0;
    for (const pair<vector<pair<ll, int>>, int> &pa : mcnt) {
        const vector<pair<ll, int> > &c1 = pa.first;
        vector<pair<ll, int> > c2 = c1;
        for (auto &elem : c2) {
            assert(elem.second != 0);
            assert(elem.second < 3);
            elem.second = 3 - elem.second;
        }
        if (mcnt.count(c2)) {
            ans2 += max(pa.second, mcnt[c2]);
        } else {
            ans2 += pa.second * 2;
        }
    }
    ans2 /= 2;
    ans += ans2;
    cout << ans << "\n";
}

void prepare() {

}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);


    prepare();

    int t = 1;
    //cin >> t;
    //t = nxt();
    forn(i, t) {
        solve();
    }

    cerr << "Time " << clock() / (double) CLOCKS_PER_SEC << endl;
    return 0;
}


Measured memory_bytes: 18584