#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long int int64;

const int N = (int) 1e5 + 100;
bool isP[N];

vector <int> ps;
vector <pair <long long, long long>> ph;

long long getRand()
{
    return abs((long long) rand() << 48) ^ ((long long) rand() << 32) ^ ((long long) rand() << 16) ^ (long long) rand();
}

void init()
{
    memset(isP, true, sizeof isP);

    for (int i = 2; i < N; i++)
    {
        if (!isP[i])
            continue;
        ph.emplace_back(getRand(), getRand());
        ps.push_back(i);
        for (long long j = i * 1LL * i; j < N; j += i)
            isP[j] = false;
    }
}

int getSqrt(long long x)
{
    long long l = 0, r = min(x, (long long)1e6);
    while (r - l > 1)
    {
        long long m = (l + r) / 2;
        if (m * m <= x)
            l = m;
        else
            r = m;
    }
    if (l * l != x)
        return -1;
    return l;
}

int main(int,  char **)
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

    init();

    eprintf("sz = %d\n", (int) ps.size());

    int n;
    scanf("%d", &n);

    map <pair <long long, long long>, int> cnt;

    int ans = 0;
    for (int it = 0; it < n; it++)
    {
//        eprintf("it = %d\n", it);
        long long x;
        scanf("%lld", &x);

        long long h1 = 0, h2 = 0;
        for (int i = 0; i < (int) ps.size() && ps[i] <= 3e3; i++)
        {
            //eprintf("i = %d\n", i);
            int p = ps[i];
            
            if (x % p == 0)
            {
                int k = 0;
                while (x % p == 0)
                {
                    x /= p;
                    k++;
                }
                k %= 3;
                if (k == 1)
                {
                    h1 ^= ph[i].first;
                    h2 ^= ph[i].second;
                }
                else if (k == 2)
                {
                    h1 ^= ph[i].second;
                    h2 ^= ph[i].first;
                }
            }
        }


        if (x != 1)
        {
//            eprintf("??\n");
            int pos = lower_bound(ps.begin(), ps.end(), x) - ps.begin();
            if (pos != (int) ps.size() && ps[pos] == x)
            {
                h1 ^= ph[pos].first;
                h2 ^= ph[pos].second;
            }
            else
            {
                int sqrt = getSqrt(x);
                
                if (sqrt == -1)
                {    
                    ans++;
                    continue;
                }

                pos = lower_bound(ps.begin(), ps.end(), sqrt) - ps.begin();
                h1 ^= ph[pos].second;
                h2 ^= ph[pos].first;
            }
        }

//        eprintf("%lld %lld\n", h1, h2);
        cnt[make_pair(h1, h2)]++;
        if (!cnt.count(make_pair(h2, h1)))
            cnt[make_pair(h2, h1)] = 0;
    }
 //   eprintf("!!\n");

    for (auto &p : cnt)
    {
        auto key = p.first;
        auto value = p.second;

        if (key.first == 0)
        {
            ans++;
            continue;
        }

        if (key.second < key.first)
            continue;

        ans += max(value, cnt[make_pair(key.second, key.first)]);
        
    }

    printf("%d\n", ans);


	return 0;
}




Measured memory_bytes: 10876