#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>
#include <unistd.h>
#include <stdint.h>
#include <math.h>
 
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T = ll> constexpr T TEN(int n) {return (n==0)?1:10*TEN<T>(n-1);}
template<class T> using V = vector<T>;

typedef __int128 int128_t;
typedef unsigned __int128 uint128_t;

static inline uint64_t ex_gcd(uint64_t y){
  int i;
  uint64_t u, v;
  u = 1; v = 0;
  uint64_t x = 1LL<<63;

  for(i=0;i<64;i++){
    if(u&1){
      u = (u + y) / 2;
      v = v/2 + x;
    }
    else {
      u >>= 1; v >>= 1;
    }
  }

  return -v;
} 


static uint64_t MR(uint128_t x, uint64_t m, uint64_t n){
  int64_t z = (x >> 64) - ((((uint64_t) x * m) * (uint128_t) n) >> 64);
  return z < 0 ? z + n : z;
}

static uint64_t RM(uint64_t x, uint64_t r2, uint64_t m, uint64_t n){
  return MR((uint128_t) r2 * x, m, n);
}

static uint64_t mulmod64(uint64_t x, uint64_t y, uint64_t m, uint64_t n){
  return MR((uint128_t) x*y, m, n);
}


int jacobi(int64_t a, uint64_t n){
  uint64_t t;
  int j = 1;
  while(a){
    if(a<0){
      a = -a;
      if((n&3)==3) j = -j;
    }
    int ba = __builtin_ctzll(a);
    a >>= ba;
    if(((n&7)==3||(n&7)==5) && (ba&1)) j = -j;
    if((a&n&3)==3) j = -j;
    t = a; a = n; n = t;
    a %= n;
    if(a>n/2) a-=n;
  }
  return n == 1 ? j : 0;
}


static inline uint64_t addmod64(uint64_t x, uint64_t y, uint64_t n){
  return x + y >= n ? x + y - n : x + y;
}

static inline uint64_t submod64(uint64_t x, uint64_t y, uint64_t n){
  return x >= y  ? x - y : x - y + n;
}



int is_prime64(const uint64_t n){
  if(n <= 1) return 0;
  if(n <= 3) return 1;
  if(!(n & 1)) return 0;

  const uint64_t one = -1ULL % n + 1;
  const uint64_t r2 = (uint128_t) (int128_t) -1 % n + 1;
  const uint64_t m = ex_gcd(n);

  {
    uint64_t d = (n-1) << __builtin_clzll(n-1);
    uint64_t t = one << 1;
    if(t >= n) t -= n;
    for(d<<=1;d;d<<=1){
      t = mulmod64(t, t, m, n);
      if(d>>63){
        t <<= 1;
        if(t>=n) t -= n;
      }
    }
    if(t != one){
      uint64_t x = (n-1) & -(n-1);
      uint64_t mone = n - one;
      for(x>>=1;t!=mone;x>>=1){
        if(x == 0) return 0;
        t = mulmod64(t, t, m, n);
  //      if(t == one) return 0;
      }
    }
  }


  {
    int64_t D = 5;
    int i;
    for(i=0;jacobi(D, n) != -1 && i<64;i++){
      if(i==32){
        uint32_t k = round(sqrtl(n));
        if(k*k == n) return 0;
      }
      if(i&1) D -= 2;
      else D += 2;
      D = -D;
    }
//    if(i==64) puts("ERROR");

    uint64_t Q = RM(D < 0 ? (1-D)/4%n : n - (D-1)/4%n, r2, m, n);

    uint64_t u, v, Qn;
    uint64_t k = (n+1) << __builtin_clzll(n+1);
    u = one; v = one;
    Qn = Q;
    D %= (int64_t) n;
    D = RM(D < 0 ? n+D : D, r2, m, n);
    for(k<<=1;k;k<<=1){
      u = mulmod64(u,v,m,n);
      v = submod64(mulmod64(v,v,m,n), addmod64(Qn, Qn, n), n);
      Qn = mulmod64(Qn, Qn, m, n);
      if(k>>63){
        uint64_t uu = addmod64(u, v, n);
        if(uu&1) uu += n;
        uu >>= 1;
        v = addmod64(mulmod64(D,u,m,n), v, n);
        if(v&1) v += n;
        v >>= 1;
        u = uu;
        Qn = mulmod64(Qn, Q, m, n);
      }
    }

    if(u == 0 || v == 0) return 1;
    uint64_t x = (n+1) & ~n;
    for(x>>=1;x;x>>=1){
      u = mulmod64(u,v,m,n);
      v = submod64(mulmod64(v,v,m,n), addmod64(Qn, Qn, n), n);
      if(v == 0) return 1;
      Qn = mulmod64(Qn, Qn, m, n);
    }
  }

  return 0;
}

struct Prime {
    int n;
    vector<bool> used;
    vector<int> pr;
    vector<ull> bpr;
    Prime(int n) : n(n) {
        used = vector<bool>(n+1, false);
        for (int i = 2; i <= n; i++) {
            if (used[i]) continue;
            pr.push_back(i);
            bpr.push_back(((__int128(1)<<64)+i-1) / i);
            for (int j = 2*i; j <= n; j += i) {
                used[j] = true;
            }
        }
    }    
    map<ll, int> fact(ll x) {
        assert(x <= (ll)n*n);
        int pc = (int)pr.size();
        map<ll, int> mp;
        for (int i = 0; i < pc; i++) {
            ll d = pr[i]; ull rd = bpr[i];
//            if (x < d*d) break; 枝刈り
            while (true) {
                ll xd = __int128(x)*rd >> 64;
                if (xd * d != x) break;
                x = xd;
                mp[d]++;
            }
        }
        if (x > 1) mp[x]++;
        return mp;
    }
};



template<class T>
T gcd(T a, T b) {
//    a = abs(a); b = abs(b);
    if (b == 0) return a;
    return gcd(b, a%b);
}

template<class T, class U>
T pow_mod(T x, U n, T md) {
    assert(n>=0);
    x %= md;
    T r = 1 % md;
    while (n) {
        if (n & 1) r = (r * x) % md;
        x = (x * x) % md;
        n >>= 1;
    }
    return r;
}

/// g:gcd(a, b), ax+by=g
template<class T> struct EG { T g, x, y; };
template<class T>
EG<T> ext_gcd(T a, T b) {
    if (b==0) {
        if (a >= 0) return EG<T>{a, 1, 0};
        else return EG<T>{-a, -1, 0};
    } else {
        auto e = ext_gcd<T>(b, a%b);
        return EG<T>{e.g, e.y, e.x-a/b*e.y};
    }
}

template<class T>
T inv_mod(T x, T md) {
    auto r = ext_gcd(x, md);
    auto z = r.x;
    return (z % md + md) % md;
}


bool isPrime(ll n) {
    return is_prime64(n);
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    ll d = n-1;
    while (d % 2 == 0) d /= 2;
    vector<ll> alist{2,3,5,7,11,13,17,19,23,29,31,37}; // n < 2^64
    for (ll a: alist) {
        if (n <= a) break;
        ll t = d;
        ll y = pow_mod<__int128>(a, t, n); //over
        while (t != n-1 && y != 1 && y != n-1) {
            y = __int128(y)*y % n; //flow
            t <<= 1;
        }
        if (y != n-1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}

ll f(ll x, ll n) { return __int128_t(x)*x % n + 1 % n; }
ll pollard_single(ll n){
	ll i,x,y,p;
	if(isPrime(n)) return n;
	if(!(n&1)) return 2;
	for(i=1;i<40;i++){
		x=i; y=f(x,n); p=gcd(y-x,n);
		while(p==1) {x=f(x,n); y=f(f(y,n),n); p=gcd((y-x+n)%n,n)%n;}
		if(p==0||p==n) continue;
		return p;
	}
    assert(false);
}

#include <inttypes.h>
#define nelems(x) (sizeof(x) / sizeof((x)[0]))

V<int> multiplier = {3, 5, 7, 11, 13, 17, 19};//, 3, 5, 7, 11, 3*5, 3*7, 3*11, 5*7, 5*11, 7*11, 3*5*7, 3*5*11, 3*7*11, 5*7*11, 3*5*7*11};

ll gc = 0;
uint64_t SQUFOF( uint64_t N )
{
    if (isPrime(N)) return N;
    if (N % 2 == 0) return 2;
    for (int d: multiplier) {
        if (N % d == 0) return d;
    }
    __int128 D;
    uint64_t Po, P, Pprev, Q, Qprev, q, b, r, s;
    uint32_t L, B, i;
    s = (uint64_t)(sqrtl(N)+0.5);
    if (s*s == N) return s;
    for (int k = 0; k < (1 << int(multiplier.size())); k++) {
        D = N;
        for (int i = 0; i < int(multiplier.size()); i++) {
            if (k & (1<<i)) D *= multiplier[i];
        }
        Po = Pprev = P = sqrtl(D);
        Qprev = 1;
        Q = D - Po*Po;
        L = 2 * sqrtl( 2*s );
        B = 3 * L;
        for (i = 2 ; i < B ; i++) {                
            b = 0;
            for (int x = 1; x < 5; x++) {
                if (Po+P < (x+1)*Q) {
                    b = x;
                    break;
                }
            }
//            if (Po+P < 2*Q) b = 1;
            if (!b) b = (uint64_t)((Po + P)/Q);

            P = b*Q - P;
            q = Q;
            Q = Qprev + b*(Pprev - P);
            if ((i & 1) == 0) {
                gc++;
                if ((Q & 3) <= 1) {
                    r = (uint64_t)(sqrtl(Q)+0.5);
                    if (r * r == Q) break;
                }
            }
            Qprev = q;
            Pprev = P;
        };
        if (i >= B) continue;
        b = (uint64_t)((Po - P)/r);
        Pprev = P = b*r + P;
        Qprev = r;
        Q = (D - Pprev*Pprev)/Qprev;
        i = 0;
        do {
            b = 0;
            for (int x = 1; x < 5; x++) {
                if (Po+P < (x+1)*Q) {
                    b = x;
                    break;
                }
            }
//            if (Po+P < 2*Q) b = 1;
            if (!b) b = (uint64_t)((Po + P)/Q);
//            b = (uint64_t)((Po + P)/Q);
            Pprev = P;
            P = b*Q - P;
            q = Q;
            Q = Qprev + b*(Pprev - P);
            Qprev = q;
            i++;
        } while (P != Pprev);
        r = gcd(N, Qprev);
        if (r != 1 && r != N) return r;
    }
    return 0;
}

V<ll> pollard(ll n) {
    if (n == 1) return {};
    ll x;
//    x = pollard_single(n);
    x = SQUFOF(n);
    if (x == n) return {x};
    V<ll> le = pollard(x);
    V<ll> ri = pollard(n/x);
    for (ll d: ri) le.push_back(d);
    return le;
}

const int MP = 100100;
 
ll mul(ll a, ll b) {
    if (TEN(12)/a < b) return TEN(12);
    return a*b;
}
 
int main() {
    Prime pr(MP);
    using P = pair<ll, ll>;
    map<ll, P> g;
    int n;
    scanf("%d", &n);
    bool one = false;
    for (int i = 0; i < n; i++) {
        ll s;
        scanf("%lld", &s);
        auto facv = pollard(s);
        sort(begin(facv), end(facv));
        int Z = int(facv.size());
        int L = 0;
        ll d0 = 1, d1 = 1;
        while (L < Z) {
            int R = L+1;
            while (R < Z && facv[R] == facv[L]) R++;
            P p = P{facv[L], R-L};
            p.second %= 3;
            if (p.second == 1) {
                d0 = mul(d0, p.first);
                d1 = mul(d1, p.first);
                d1 = mul(d1, p.first);
            } else if (p.second == 2) {
                d0 = mul(d0, p.first);
                d0 = mul(d0, p.first);
                d1 = mul(d1, p.first);
            }
            L = R;
        }
//        map<ll, int> fac;
//        for (auto d: facv) fac[d]++;
//        map<ll, int> fac = pr.fact(s);
//        for (auto p: fac) {
//        }
        if (d0 == 1) {
            one = true;
            continue;
        }
        if (d0 < d1) {
            g[d0].first++;
        } else {
            g[d1].second++;
        }
    }
 
    int ans = 0;
    for (auto p: g) {
        ans += max(p.second.first, p.second.second);
    }
    cout << ans + (one ? 1 : 0) << endl;
    return 0;
}


Measured memory_bytes: 7296