#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 7000000;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<long long> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> primes;
  vector<bool> is_composite(N);
  is_composite[1] = 1;
  for (int i = 2; i < N; i++) {
    if (!is_composite[i]) {
      primes.push_back(i);
      for (long long j = i * 1LL * i; j < N; j += i) {
        is_composite[j] = 1;
      }
    }
  }
  map<long long, long long> have, rest;
  set<pair<long long, long long>> pairs;
  for (int i = 0; i < n; i++) {
    long long x = a[i];
    if (have.count(a[i])) {
      continue;
    }
    have[a[i]] = 1;
    rest[a[i]] = 1;
    for (auto& p : primes) {
      if (p * 1LL * p * p > x) {
        break;
      }
      int cnt = 0;
      while (x % p == 0) {
        cnt = (cnt + 1) % 3;
        x /= p; 
      }
      for (int j = 0; j < cnt; j++) {
        have[a[i]] *= p;
      }
      for (int j = 0; j < (3 - cnt) % 3; j++) {
        rest[a[i]] *= p;
      } 
    }
    debug(x);
    /*if (!is_composite[x]) {
      have[a[i]] *= x;
      rest[a[i]] *= x * x;
    } else { */
      long long root = sqrt(x);
      while (root * root < x) {
        root++;
      }
      while (root * root > x) {
        root--;
      }
      debug(root);
      debug(x);
      debug(a[i]);
      if (root * root == x && !is_composite[root]) {
        have[a[i]] *= x;
        rest[a[i]] *= root;
        debug(have[a[i]]);
      } else {
        have[a[i]] *= x;
        rest[a[i]] *= x * x;
      }
    // }
    pairs.insert(make_pair(min(have[a[i]], rest[a[i]]), max(have[a[i]], rest[a[i]])));
  }
  cerr << "have\n";
  debug(have);
  cerr << "rest\n";
  debug(rest);
  // map<long long, vector<long long>> with_have, with_rest;
  map<long long, long long> with_have, with_rest;
  for (int i = 0; i < n; i++) {
    // with_have[have[a[i]]].push_back(a[i]);
    // with_rest[rest[a[i]]].push_back(a[i]);
    with_have[have[a[i]]]++;
    with_rest[rest[a[i]]]++;
  }
  debug(with_have);
  debug(with_rest);
  long long ans = 0;
  debug(pairs);
  for (auto& p : pairs) {
    if (p.first == 1 && p.second == 1) {
      ans++;
    } else {
      ans += max(max(with_have[p.first], with_rest[p.second]), max(with_rest[p.first], with_have[p.second]));
    }
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 47472