#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int i = 0; i < n; i++ ){ cout << x[i] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second
     
using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ ll x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head

struct Millar{
  // const vl v = { 2 , 7 , 61 }; // < 4,759,123,141
  const vl v = { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 }; // ??
  ll modpow( __int128 x , __int128 k , __int128 mo ){
    ll res = 1;
    while( k ){
      if( k & 1 ) res = res * x % mo;
      k /= 2;
      x = x * x % mo;
    }
    return res;
  }
  bool check( ll n ){
    if( n < 2 ) return false;
    ll d = n - 1, s = 0;
    while( d % 2 == 0 ) d /= 2, s++;
    YYS( a , v ){
      if( a == n ) return true;
      if( modpow( a , d , n ) != 1 ){
	bool ok = true;
	REP( r , s ) if( modpow( a , d * PW(r) , n ) == n-1 ) ok = false;
	if( ok ) return false;
      }
    }
    return true;
  }
};


struct Rho{
  mt19937 mt;
  Millar isp;
  ll c;
  Rho(){
    mt.seed( time(NULL) );
  }
  inline ll f( __int128 x , __int128 n ){
    return ( x*x%n + c ) % n;
  }
  ll check( ll n ){
    if( n == 4 ) return 2;
    c = mt() % n;
    ll x = mt() % n;
    ll y = x;
    ll d = 1;
    while( d == 1 ){
      x = f(x,n);
      y = f(f(y,n),n);
      d = __gcd( abs(x-y) , n );
    }
    if( d == n ) return -1;
    return d;
  }
  vl factor( ll n ){
    if( n <= 1 ) return {};
    if( isp.check( n ) ) return { n };
    ll res = -1;
    while( res == -1 ) res = check( n );
    vl fa = factor( res );
    vl fb = factor( n / res );
    fa.insert( fa.end() , ALL(fb) );
    return fa;
  }
} rho;


const int N = 100010;

bool np[N];
vi pri;

int n;

ll a[100010];

map<vl,int> ma;

void inc( vl v ){
  if( ma.find( v ) == ma.end() ){
    ma[v] = 1;
  } else {
    ma[v]++;
  }
}

vl flip( vl v ){
  for( int i = 1; i < SZ(v); i += 2 ){
    v[i] = 3 - v[i];
  }
  return v;
}

Millar isp;

int main(){


  ll cur = 0;
  n = in();
  bool f = false;
  REP( i , n ){
    if( i % 100 == 0 ){
      // SHOW( i );
    }
    a[i] = in();
    vl fs = rho.factor( a[i] );
    SORT( fs );
    ll prv = -1;
    ll cnt = 0;
    vl ps(0);
    YYS( w , fs ){
      if( w != prv ){
	if( cnt % 3 != 0 ){
	  ps.pb( prv );
	  ps.pb( cnt % 3 );
	}
	cnt = 0;
	prv = w;
      }
      cnt++;
    }
    if( cnt % 3 != 0 ){
      ps.pb( prv );
      ps.pb( cnt % 3 );
    }
    /*
    cout << a[i] << endl;
    SHOWA( fs , SZ(fs) );
    SHOWA( ps , SZ(ps) );
    */
    if( SZ(ps) == 0 ){
      f = true;
    } else {
      cur += SZ(ps);
      inc( ps );
    }
  }
  
  ll ans = 0;
  
  if( f ){
    ans = 1;
  }
  
  int cnt = 0;
  YYS( w , ma ){
    vl v = w.fi;
    vl u = flip( v );
    if( ma.find( u ) != ma.end() ){
      ans += max( ma[v] , ma[u] );      
      ma[v] = ma[u] = 0;
    } else {
      ans += ma[v];
    }
  }
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 15616