#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <functional>
#include <unordered_map>
#include <unordered_set>

#include <cmath>
using namespace std;

#define LLD_SPEC "%lld"

using TFact = vector<pair<long long, int>>;

TFact Factorize(long long x) {
    TFact result;
    for (long long i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            result.push_back(make_pair(i, 0));
            while (x % i == 0) {
                x /= i;
                ++result.back().second;
            }
        }
    }
    if (x > 1) {
        result.push_back(make_pair(x, 1));
    }
    return result;
}

bool IsGoodFactorization(const TFact& f) {
    for (const pair<long long, int>& p : f) {
        if (p.second != 1 && p.second != 2) {
            return false;
        }
    }
    return true;
}

bool IsPrime(long long x) {
    TFact f = Factorize(x);
    return f.size() == 1 && f[0].second == 1;
}

const long long LIM = 1e10;

vector<long long> primes;

int GetOnes(vector<long long>& nums) {
    int count = 0;
    for (int i = 0; i < (int) nums.size(); ) {
        if (nums[i] == 1) {
            ++count;
            swap(nums[i], nums.back());
            nums.pop_back();
        } else {
            ++i;
        }
    }
    return count;
}

void FillNewNums(vector<long long>& nums, long long p, vector<vector<long long>>& newNums) {
    for (int i = 0; i < (int) nums.size(); ++i) {
        int pw = 0;

        if ((nums[i] % (p * p)) == 0) {
            pw = 2;
            nums[i] /= (p * p);
        } else if ((nums[i] % p) == 0) {
            pw = 1;
            nums[i] /= p;
        } else {
            pw = 0;
        }

        newNums[pw].push_back(nums[i]);
    }
}

bool IsSquare(long long x, long long& y) {
    y = sqrt(x);
    while (y * y < x) {
        ++y;
    }
    while (y * y > x) {
        --y;
    }
    return y * y == x;
}

int GetResult(int fromIndex, vector<long long>& n1, vector<long long>& n2) {
    if (n1.empty()) {
        return n2.size();
    }

    if (n2.empty()) {
        return n1.size();
    }

    int firstOnes = GetOnes(n1);
    int secondOnes = GetOnes(n2);
    int result = max(firstOnes, secondOnes);

    for (int index = fromIndex; index < (int) primes.size(); ++index) {
        long long p = primes[index];

        vector<vector<long long>> newNums1(3);
        FillNewNums(n1, p, newNums1);

        vector<vector<long long>> newNums2(3);
        FillNewNums(n2, p, newNums2);

        n1 = newNums1[0];
        n2 = newNums2[0];

        result += GetResult(index + 1, newNums1[1], newNums2[2]);
        result += GetResult(index + 1, newNums1[2], newNums2[1]);

        if (n1.empty()) {
            return n2.size() + result;
        }
        if (n2.empty()) {
            return n1.size() + result;
        }
    }

    unordered_map<long long, int> c1;
    unordered_map<long long, int> c2;

    for (long long x : n1) {
        ++c1[x];
    }
    for (long long x : n2) {
        ++c2[x];
    }

    unordered_set<long long> u1, u2;

    for (const pair<long long, int>& p1 : c1) {
        long long x = p1.first;
        long long y;

        if (IsSquare(x, y)) {
            result += max(c1[x], c2[y]);
            u1.insert(x);
            u2.insert(y);
        }
    }

    for (const pair<long long, int>& p2 : c2) {
        long long x = p2.first;
        long long y;

        if (IsSquare(x, y)) {
            result += max(c1[y], c2[x]);
            u1.insert(y);
            u2.insert(x);
        }
    }

    for (const pair<long long, int>& p1 : c1) {
        if (u1.find(p1.first) == u1.end()) {
            result += p1.second;
        }
    }

    for (const pair<long long, int>& p2 : c2) {
        if (u2.find(p2.first) == u2.end()) {
            result += p2.second;
        }
    }

    return result;
}

int GetResult(vector<long long>& nums) {
    int result = (GetOnes(nums) > 0);

    for (int index = 0; index < (int) primes.size(); ++index) {
        long long p = primes[index];

        vector<vector<long long>> newNums(3);

        FillNewNums(nums, p, newNums);
        nums = newNums[0];

        result += GetResult(index + 1, newNums[1], newNums[2]);

        if (nums.empty()) {
            return result;
        }
    }

    unordered_map<long long, int> count;
    for (long long x : nums) {
        ++count[x];
    }

    unordered_set<long long> used;

    for (const pair<long long, int>& p : count) {
        long long x = p.first;
        long long y;

        if (IsSquare(x, y)) {
            int c1 = p.second;
            int c2 = count[y];

            result += max(c1, c2);

            used.insert(y);
            used.insert(x);
        }
    }

    for (const pair<long long, int>& p : count) {
        if (used.find(p.first) == used.end()) {
            result += p.second;
        }
    }

    return result;
}

int main() {
    /*
    freopen("input.txt", "w", stdout);
    const int N = 1e5;
    cout << N << endl;
    for (int i = 0; i < N; ++i) {
        cout << (rand() % LIM) + 1 << endl;
    }
    return 0;
    */
    // freopen("input.txt", "r", stdin);
    int n;
    scanf("%d", &n);
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        scanf(LLD_SPEC, &a[i]);
    }

    for (long long i = 2; i * i * i <= LIM; ++i) {
        if (IsPrime(i)) {
            primes.push_back(i);
        }
    }

    for (long long p : primes) {
        long long value = p * p * p;
        for (int j = 0; j < n; ++j) {
            while ((a[j] % value) == 0) {
                a[j] /= value;
            }
        }
    }

    printf("%d\n", GetResult(a));

    return 0;
}

Measured memory_bytes: 3316