#include <iostream>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const ll MAX_A = 1e10 + 5;
const int MAX_P = 1e5 + 5;

ll cb (ll x) {
  return x * x * x;
}

ll sq (ll x) {
  return x * x;
}

int sieve [MAX_P];
vector<ll> primes;
vector<ll> smps;

ll reduce (ll x) {
  for (ll p : smps) {
    while (x % cb(p) == 0) {
      x /= cb(p);
    }
  }
  return x;
}

#define DEBUG(...) cerr << __VA_ARGS__ << endl;

#ifndef CDEBUG
#undef DEBUG
#define DEBUG(...) ((void)0);
#define NDEBUG
#endif

#define ran(i, a, b) for (auto i = (a); i < (b); i++)

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
const int mod = 1e9 + 7;
#ifndef M_PI
const double M_PI = acos(-1.0);
#endif

//!escape Fast mod mult, Rabbin Miller prime check, Pollard rho factorization O(p^0.5)

//!begin_codebook
//!start

struct ModArithm {
  //!pause
  ull q = 0; // (1<<(shift+64))/n
  char shift = -1;
  //!unpause
  ull n;
  ld rec;
  ModArithm(ull _n) : n(_n) { // n in [2, 1<<63)
    rec = 1.0L / n;
    //!pause
    ull rem = 1;
    while (rem < n) {
      ++shift;
      rem <<= 1;
    }
    for (int i = 63; i >= 0; --i) {
      if (rem >= n) {
        q |= 1LL << i;
        rem -= n;
      }
      rem *= 2;
    }
    //!unpause
  }
  // a, b in [0, min(2*n, 1<<63))
  ull multf(ull a, ull b) {
    ull mult = (ld)a * b * rec + 0.5L;
    ll res = a * b - mult * n;
    if (res < 0) res += n;
    return res; // in [0, n-1)
  }
  //!pause
#ifndef ONLINE_JUDGE
  ull multa(ll a, ll b) { // a, b in [0, min(2*n, 1<<63))
    ull res;
    ull tmp;
    __asm__(
      "mulq %[b];\n\t"          // a*b
      "movq %%rax, %[res];\n\t" // ab_l = (a*b) & ((1 <<
                                // 64)-1)
      "movq %%rdx, %[tmp];\n\t" // ab_h = (a*b) >> 64
      "mulq %[q];\n\t"          // ab_l * q
      "movq %[tmp], %%rax;\n\t"
      "movq %%rdx, %[tmp];\n\t" // abq_m = (ab_l * q) >>
                                // 64
      "mulq %[q];\n\t"          // ab_h * q
      "addq %[tmp], %%rax;\n\t" // abq_m += (ab_h * q) &
                                // ((1 << 64)-1)
      "adcq $0, %%rdx;\n\t" // abq_h = ((ab_h * q) >> 64)
                            // + carry
      "shrdq %%cl, %%rdx, %%rax;\n\t" // d = (a*b)/n =
                                      // (abq_m >> shift)
                                      // | (abq_h << (64
                                      // -shift))
      "mulq %[n];\n\t"                // d*n
      "subq %%rax, %[res];\n\t"       // ab_l - = dn_l
      : [res] "=&r"(res), [tmp] "=&r"(tmp)
      : [a] "%a"(a), [b] "d"(b), [q] "r"(q),
      [shift] "c"(shift), [n] "rm"(n)
      : "cc");
    return res; // in [0, 2n-1)
  }
  ull multi(ull a, ull b) {
    unsigned __int128 mult = a;
    mult *= b;
    ull prod =
      (((mult >> 64) * q) +
        ((unsigned __int128)(ull)mult * q >> 64)) >>
      shift;
    return (ull)mult - prod * n;
  }
  ull fix(ull a) {
    if (a >= n) a -= n;
    return a;
  }
  ull mult(ull a, ull b) { return fix(multi(a, b)); }
#endif
  //!unpause
  ull sqp1(ull a) { return multf(a, a) + 1; }
};
//!finish
//!start

ull pow_mod(ull a, ull n, ModArithm &arithm) {
  ull res = 1;
  for (ull i = 1; i <= n; i <<= 1) {
    if (n & i) res = arithm.multf(res, a);
    a = arithm.multf(a, a);
  }
  return res;
}
//!finish
//!start

vector<char> small_primes = {
  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

bool is_prime(ull n) { // n <= 1<<63, 1M rand/s
  ModArithm arithm(n);
  if (n == 2 || n == 3) return true;
  if (!(n & 1) || n == 1) return false;
  int s = __builtin_ctzll(n - 1);
  ull d = (n - 1) >> s;
  for (ull a : small_primes) {
    if (a >= n) break;
    a = pow_mod(a, d, arithm);
    if (a == 1 || a == n - 1) continue;
    ran(r, 1, s) {
      a = arithm.multf(a, a);
      if (a == 1) return false;
      if (a == n - 1) break;
    }
    if (a != n - 1) return false;
  }
  return true;
}
//!finish
//!pause

#ifdef ONLINE_JUDGE
ll __gcd(ll a, ll b) {
  if (a) return __gcd(b % a, a);
  return b;
}
#endif

//!unpause
//!start

ll pollard_rho(ll n) {
  ModArithm arithm(n);
  int cum_cnt = 64 - __builtin_clzll(n);
  cum_cnt *= cum_cnt / 5 + 1;
  while (true) {
    ll lv = rand() % n;
    ll v = arithm.sqp1(lv);
    int idx = 1;
    int tar = 1;
    while (true) {
      ll cur = 1;
      ll v_cur = v;
      int j_stop = min(cum_cnt, tar - idx);
      for (int j = 0; j < j_stop; ++j) {
        cur = arithm.multf(cur, abs(v_cur - lv));
        v_cur = arithm.sqp1(v_cur);
        ++idx;
      }
      //!pause
      // cur = arithm.fix(cur);
      //!unpause
      if (!cur) {
        for (int j = 0; j < cum_cnt; ++j) {
          ll g = __gcd(abs(v - lv), n);
          if (g == 1) {
            v = arithm.sqp1(v);
          } else if (g == n) {
            break;
          } else {
            return g;
          }
        }
        break;
      } else {
        ll g = __gcd(cur, n);
        if (g != 1) return g;
      }
      v = v_cur;
      idx += j_stop;
      if (idx == tar) {
        lv = v;
        tar *= 2;
        v = arithm.sqp1(v);
        ++idx;
      }
    }
  }
}
//!finish
//!start


map<ll, int> prime_factor(
      ll n, map<ll, int> *res = NULL) {
  // n <= 1<<62, ~1000/s (<500/s on CF)
  if (!res) {
    map<ll, int> res_act;
    for (int p : small_primes) {
      while (!(n % p)) {
        ++res_act[p];
        n /= p;
      }
    }
    if (n != 1) prime_factor(n, &res_act);
    return res_act;
  }
  if (is_prime(n)) {
    ++(*res)[n];
  } else {
    ll factor = pollard_rho(n);
    prime_factor(factor, res);
    prime_factor(n / factor, res);
  }
  return map<ll, int>();
} // Usage: fact = prime_factor(n);
//!finish
//!end_codebook

int blog (ll x) {
  return 63 - __builtin_clzll(x);
}

ll complm (ll x) {
  auto pfs = prime_factor(x);

  ll ans = 1;
  for (auto it = pfs.begin(); it != pfs.end(); it++) {
    if (it->second == 1) {
      if (blog(ans) + 2 * blog(it->first) > 40) return -1;
      ans *= sq(it->first);
    } else if (it->second == 2) {
      if (blog(ans) + blog(it->first) > 40) return -1;
      ans *= it->first;
    }
  }
  return ans;
}

const int MAX_N = 1e5 + 5;

ll arr [MAX_N];

int main () {
  for (int i = 2; i < MAX_P; i++) {
    if (!sieve[i]) {
      primes.push_back(i);
      if (cb(i) < MAX_A) {
        smps.push_back(i);
      }
      for (int j = i; j < MAX_P; j += i) {
        sieve[j] = 1;
      }
    }
  }

  int n;
  cin >> n;
  
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    arr[i] = reduce(arr[i]);
  }

  map<ll, int> cnt;
  for (int i = 0; i < n; i++) {
    if (cnt.count(arr[i]) == 0) {
      cnt[arr[i]] = 0;
    }
    cnt[arr[i]]++;
  }

  set<ll> seen;
  int ans = 0;
  for (auto it = cnt.begin(); it != cnt.end(); it++) {
    if (it->first == 1) {
      ans++;
    } else {
      if (!seen.count(it->first)) {
        ll co = complm(it->first);
        int cco = 0;
        if (cnt.count(co) != 0) {
          cco = cnt[co];
        }

        seen.insert(co);
        ans += max(it->second, cco);
        // cerr << it->first << " " << co << " " << it->second << " " << cco << endl;
      }
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 13816