// Slower C++ solution:
#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>



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 = ll> T gcd(T a, T b) {return (b==0) ? a : gcd(b, a%b);}

template<class T = ll> T lcm(T a, T b) {return a/gcd(a, b)*b;}



/// g:gcd(a, b), ax+by=g

template<class T> struct EG { T g, x, y; };

template<class T = ll>

EG<T> ext_gcd(T a, T b) {

    if (b==0) {

        return EG<T>{a, 1, 0};

    } else {

        auto e = ext_gcd(b, a%b);

        return EG<T>{e.g, e.y, e.x-a/b*e.y};

    }

}



template<class T>

T pow(T x, ll n, T md) {

    T r = 1;

    while (n) {

        if (n & 1) r = (r*x)%md;

        x = (x*x)%md;

        n >>= 1;

    }

    return r;

}





ll rand_int(ll l, ll r) { //[l, r)

    using D = uniform_int_distribution<ll>;

    static random_device rd;

    static mt19937 gen(rd());

    return D(l, r-1)(gen);

}



const int MP = 100100;

vector<int> pr;

vector<ull> bpr;



void first() {

    bool used[MP] = {};

    for (int i = 2; i < MP; i++) {

        if (used[i]) continue;

        pr.push_back(i);

        ull x = ((__int128(1)<<64) + i-1 ) / i;

        bpr.push_back(x);

        for (int j = 2*i; j < MP; j += i) {

            used[j] = true;

        }

    }

}



map<ll, int> factsmall(ll n) {

    int pc = (int)pr.size();

    map<ll, int> mp;

    while (n % 2 == 0) {

        n /= 2;

        mp[2]++;

    }

    while (n % 3 == 0) {

        n /= 3;

        mp[3]++;

    }

    for (int i = 2; i < pc; i++) {

        ll d = pr[i]; ull rd = bpr[i];

        if (n < d*d) break;

//        assert(n/d == __int128(n)*rd >> 64);

/*        ll nd = __int128(n)*rd >> 64;

        while (nd * d == n) {

            n = nd;

            mp[d]++;

        }*/

        while (true) {

            ll nd = __int128(n)*rd >> 64;

            if (nd * d != n) break;

            n = nd;

            mp[d]++;

        }

    }

    if (n > 1) mp[n]++;

    return mp;

}



bool isPrime(ll 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,1662803}; // n < 1.12e12

//    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<__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;

}





int gc = 0;



map<ll, int> prefact(ll n) {

    map<ll, int> mp;

/*    for (ll d: pr) {

        if (1000 < d) break;

        while (n % d == 0) {

            n /= d;

            mp[d]++;

        }

    }

    if (isPrime(n)) {

        mp[n]++;

        return mp;

    }*/

    map<ll, int> mp1 = factsmall(n);

    for (auto p: mp1) {

        mp[p.first] += p.second;

    }

    return mp;

}



int main() {

    first();

    using F = vector<ll>;

    map<F, F> g;

    map<F, int> a;

    int n;

    scanf("%d", &n);

    bool one = false;

    for (int i = 0; i < n; i++) {

        if (i % 1000 == 0) {

//            cout << i << " " << gc << endl;

        }

        ll s;

        scanf("%lld", &s);

        map<ll, int> fac = prefact(s);

        F d0, d1;

        for (auto p: fac) {

            p.second %= 3;

            if (p.second == 1) {

                d0.push_back(p.first);

                d1.push_back(p.first);

                d1.push_back(p.first);

            } else if (p.second == 2) {

                d0.push_back(p.first);

                d0.push_back(p.first);

                d1.push_back(p.first);

            }

        }

        sort(d0.begin(), d0.end());

        sort(d1.begin(), d1.end());

        if (d0.size() == 0) {

            one = true;

            continue;

        }

        g[d0] = d1; g[d1] = d0;

        a[d0]++;

    }



    int ans = 0;

    for (auto p: g) {

        ans += max(a[p.first], a[p.second]);

    }

    cout << ans/2 + (one ? 1 : 0) << endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1280400139946916x):
#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;

}