#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template
ll sq(ll n){
    double m = double(n);
    m = sqrt(m);
//    /cout << m << endl;
    ll t = ll(m);
    if(t * t == n) return t;
    if((t + 1) * (t + 1) == n) return t + 1;
    return -1;
}

vector<ll> primes;
void make_primes(){
    primes.pb(2);
    for(ll n = 3; n <= 2200; n++){
        bool isPrime = true;
        for(ll i = 0; primes[i] * primes[i] <= n && i < primes.size(); i++){
            if(n % primes[i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) primes.pb(n);
    }
    
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
//    cout << sq(4) << endl;
    make_primes();
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) {
        cin >> A[i];
        for(ll prime: primes){
            while(1){
                if(A[i] % (prime * prime * prime) == 0){
                    A[i] /= prime * prime * prime;
                }
                else{
                    break;
                }
            }
        }
    }
    sort(all(A));
    vector<pair<ll, int>> C;
    map<ll, int> M;
    ll num = -1;
    rep(i, N){
        if (num == A[i]){
            C.back().second++;
        }
        else{
            C.pb(mp(A[i], 1));
            M[A[i]] = (int)C.size(); // index + 1
        }
        num = A[i];
    }
    vector<int> vis(C.size(), 0);
    int ret = 0;
    // a*b^2 and a^2*b
    rep(i, C.size()){
        if(vis[i] > 0) continue;
        ll a = C[i].first;
        ll b = 1;
        for(ll prime: primes){
            if(a % (prime * prime) == 0){
                a /= (prime * prime);
                b *= prime;
            }
        }
        if(a == 1) continue;
        if(M[a * a * b] > 0){
            ret += max(C[i].second, C[M[a * a * b] - 1].second);
            vis[i] = 1, vis[M[a * a * b] - 1] = 1;
        }
        else{
            ret += C[i].second;
            vis[i] = 1;
        }
    }
    
    // a^2 and a
    for(int i = int(C.size()) - 1; i >= 0; i--){
        if(vis[i] > 0) continue;
        ll s = sq(C[i].first);
        if(s == 1) continue;
        if(s > 0){
//            cout << s << endl;
            if(M[s] > 0){
//                cout << s << " " << C[i].second << ", " << C[M[s] - 1].second << endl;
                ret += max(C[i].second, C[M[s] - 1].second);
                vis[i] = 1, vis[M[s] - 1] = 1;
            }
            else{
                ret += C[i].second;
                vis[i] = 1;
            }
        }
    }
    
    rep(i, C.size()){
        if(vis[i] == 0){
            if(C[i].first == 1) ret++;
            else ret += C[i].second;
        }
    }
    
    output(ret, 0);
    
    return 0;
}

Measured memory_bytes: 15600