//#include <bits/stdc++.h>
//#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstring>
#include<bitset>
#include<ctime>

#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define mset(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)

using namespace std;
typedef long long ll;

#ifdef local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() {
    cout << endl;
}
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) {
    for (auto x: a)
        cout << x << ' ';
    err(args...);
}
template<typename T, typename... Args>
void err(T a, Args... args) {
    cout << a << ' ';
    err(args...);
}
#else
#define dbg(...)
#endif

const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const long double eps = 1e-6;
//const int mod = 998244353;
const int maxn = 3e6;
//const int M = 3e6+10;
const int N = 2200;

//int T = 0;
//void testcase() {
//    cout << "Case #" << (++T) << ": ";
//}


int prime[N+1];
//int prim[N];
//int tot = 0;
void getPrime(){
    for(int i = 2; i <= N; ++i){

        if(!prime[i]) prime[++prime[0]] = i;
        for(int j = 1; j <= prime[0] && prime[j] <= N / i; ++j){
            prime[prime[j]*i] = 1;
            if(i%prime[j] == 0) break;
        }
    }
//    rep1(i,prime[0]){
//        dbg(i, prime[i]);
//    }

}


ll factor[100][2];
int fatCnt;
int getFactors(ll x){
    fatCnt = 0;
    ll tmp = x;
    for(int i = 1; i < prime[0] && prime[i] <= tmp; ++i){
//        dbg(i, tmp);
        factor[fatCnt][1] = 0;
        if(tmp % prime[i] == 0){
//            dbg(tmp, i, prime[i]);
            factor[fatCnt][0] = prime[i];
            while(tmp % prime[i] == 0){
                factor[fatCnt][1]++;
                tmp /= prime[i];
            }
            fatCnt++;
        }
    }
//    dbg(tmp);
    if(tmp != 1){
        ll x = sqrt(tmp + 1);
        if(x * x == tmp){
            factor[fatCnt][0] = x;
            factor[fatCnt++][1] = 2;
        }
        else{
            factor[fatCnt][0] = tmp;
            factor[fatCnt++][1] = 1;
        }
    }
    return fatCnt;
}

map<vector<pair<ll,int> > , int> M;
vector<pair<ll,int> > v;

template<class T>
void scan_d(T&ret){
    char c; ret = 0;
    while((c=getchar()) < '0' || c > '9');
    while(c>='0'&&c<='9')ret=ret*10+(c-'0'),c=getchar();
}

void work() {
    int n;
    cin >> n;
//    scan_d(n);
    bool zero = false;
    rep(i,n){
        ll x;
//        scan_d(x);
        cin >>x;
        v.clear();
        if(x == 1);
        else{
            getFactors(x);
//            dbg(x);
            rep(j,fatCnt){
                if(factor[j][1]%=3){
                    v.EB(factor[j][0], factor[j][1]);
                }
            }
        }
        if(v.size()){
            M[v]++;
        }
        else{
            zero = true;
        }

    }
    ll ans = zero;
    for(auto it = M.begin(); it != M.end(); it++){
        auto & u = it->X;
        v.clear();
        for(auto & x : u){
            v.EB(x.X, 3-x.Y);
        }

        if(M.count(v)){
            ans += max(it->Y, M[v]);
            M.erase(v);
        }
        else{
            ans += it->Y;
        }
    }
//    printf("%d\n", ans);
    cout << ans << endl;

}

int main() {
#ifdef local
    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
#endif // local
    IOS;
//    dbg(1e5*1e5/log2(1e10));
   // init();
   getPrime();
//     int t;
//     cin >> t;
//     for(;t--;)
    work();
    return 0;
}


Measured memory_bytes: 14592