#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <ctype.h>
#include <deque>
#include <queue>
#include <cstring>
#include <set>
#include <list>
#include <map>
#include <random>
#include <unordered_map>
#include <stdio.h>

using namespace std;

typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<bool> vb;
typedef std::vector<string> vs;
typedef std::vector<double> vd;
typedef std::vector<long long> vll;
typedef std::vector<std::vector<int> > vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef std::vector<std::pair<int, int> > vpi;
typedef vector<vpi> vvpi;
typedef std::pair<int, int> pi;
typedef std::pair<ll, ll> pll;
typedef std::vector<pll> vpll;

const long long mod = 1000000007;

#define all(c) (c).begin(),(c).end()
#define sz(c) (int)(c).size()
#define forn(i, a, b) for(int i = a; i < b; i++)

#define pb push_back
#define mp make_pair

int main()
{
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "rt", stdin);
//    freopen("output.txt", "wt", stdout);
//#endif
    const int LIMIT = 2500;
    vb isp(LIMIT+1, true);
    vi mindiv(LIMIT+1, 0);
    forn(i,0,LIMIT+1) mindiv[i]=i;
    int upbound = (int)sqrt((double)LIMIT);
    vi p;
    for (int m = 2; m <= upbound; m++) {
        if (isp[m]) {
            p.pb(m);
            for (int k = m * m; k <= LIMIT; k += m) {
                isp[k] = false;
                mindiv[k]=min(mindiv[k], m);
            }
        }
    }
    
    for(int m = upbound+1; m<=LIMIT; m++) {
        if (isp[m]) {
            p.pb(m);
        }
    }
    int n;
    scanf("%d", &n);
    ll a = 0;
    ll x;
    map<ll,ll> to;
    map<ll, int> cnt;
    int ans = 0;
    ll nmax = 100000000000ll;
    forn(i,0,n) {
        scanf("%lld", &x);
        ll wasx = 1;
        ll px = 1;
        bool pos = true;
        for(auto pr : p) {
            if(x == 1) break;
            int cnt = 0;
            while(x%pr == 0) {
                x/=pr;
                cnt++;
            }
            cnt = cnt%3;
            forn(ag,0,cnt) wasx *= pr;
            if(cnt>0) {
                cnt = 3- cnt;
            }
            while(cnt > 0) {
                px *= pr;
                cnt--;
                if(px > nmax) pos = false;
            }
        }
        if(x>1) {
            ll y = (ll)((sqrt((double)x)) + 0.5);
            if(y*y == x) {
                wasx *= x;
                px *= y;
                if(px > nmax) pos = false;
                x = 1;
            }
        }
        if(x>=100000) {
            ans++;
        }
        else if(x>1) {
            px*=x;
            if(px > nmax) pos = false;
            px*=x;
            if(px > nmax) pos = false;
            wasx*=x;
            cnt[wasx]++;
            to[wasx] = px;
        }
        else if(!pos) {
            ans++;
        }
        else {
            cnt[wasx]++;
            to[wasx] = px;
        }
    }
    ans*=2;
    map<ll, int> cnt2 = cnt;
    for(auto u : cnt2) {
        if(u.first == 1) {
            if(u.second > 0) ans+=2;
        }
        else {
            if(cnt[u.first] > cnt[to[u.first]]) ans += 2*cnt[u.first];
            else if(cnt[u.first] == cnt[to[u.first]]) ans += cnt[u.first];
        }
    }
    ans /=2;
    cout<<ans<<endl;
    
}



Measured memory_bytes: 20992