#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}
template<class A,size_t N,class T>void Fill(A(&a)[N],const T&v){fill((T*)a,(T*)(a+N),v);}

const ll MOD = 939561957918767; //998244353;

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m=MOD){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m=MOD){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}
//V<ll>Fac,Rac;void setF(int n,int m=MOD){Fac=Rac=V<ll>(++n);Fac[0]=1;FOR(i,1,n)Fac[i]=Fac[i-1]*i%m;Rac[n-1]=modInv(Fac[n-1],m);FORR(i,n-1,1)Rac[i-1]=Rac[i]*i%m;}
//ll comb(int a,int b,int m=MOD){return a<b||b<0?0:Fac[a]*Rac[b]%m*Rac[a-b]%m;}

const int IINF = 1e9+6;
const ll LINF = 1e18;

struct prime{
  static const int N = 2e7;
  vector<ll> pr;
  ll z[N+1];
  prime(){
    for (int i=2; i<=N; ++i) {
      if(!z[i]) pr.push_back(z[i]=i);
      for(int j=0, k, p=pr.size(); j<p && (k=pr[j])<=z[i] && i*k<=N; ++j) z[i*k]=k;
    }
  }
  bool isPrime(ll n){
    if(n<2||n%2==0) return n==2;
    __uint128_t t=n-1, d=t/(t&-t);
    for(__uint128_t a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){
      t=d;
      a=modPow(a,t,n);
      while(t!=n-1 && a!=1 && a!=n-1) a=a*a%n, t=t*2%n;
      if(a!=n-1 && t%2==0) return false;
    }
    return true;
  }
  ll pollard_single(ll n) {
    auto f = [&](ll x) { return (__int128_t(x) * x + 1) % n; };
    if (isPrime(n)) return n;
    if (n % 2 == 0) return 2;
    ll st = 0;
    while (true) {
      st++;
      ll x = st, y = f(x);
      while (true) {
        ll p = __gcd((y - x + n), n);
        if (p == 0 || p == n) break;
        if (p != 1) return p;
        x = f(x);
        y = f(f(y));
      }
    }
  }

  V<ll> pollard(ll n) {
    if(n<=N){
      V<ll> ret;
      while(n>1){
        ret.pb(z[n]);
        n /= z[n];
      }
      return ret;
    }
    ll x = pollard_single(n);
    if (x == n) return {x};
    V<ll> le = pollard(x);
    V<ll> ri = pollard(n / x);
    le.insert(le.end(), ri.begin(), ri.end());
    return le;
  }
} pr;
int n;
map<ll, P<int, int>> M;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  FOR(_, 0, n){
    ll s;
    cin >> s;
    map<ll, int> m;
    for(ll a:pr.pollard(s)) m[a]++;
    ll h = 1, r = 1;
    for(auto p:m){
      int c = p.se%3;
      if(!c) continue;
      FOR(i, 0, c)   h = lll(h) * p.fi % MOD;
      FOR(i, 0, 3-c) r = lll(r) * p.fi % MOD;
    }
    if(h > r){
      M[r].se++;
    }else{
      M[h].fi++;
    }
  }
  int ans = 0;
  for(auto p:M){
    if(p.fi==1){
      ans++;
      continue;
    }
    ans += max(p.se.fi, p.se.se);
  }
  cout << ans << endl;
}

Measured memory_bytes: 175080