#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 10;
int n, a[MAXN], cnt[MAXN], f[MAXN];
int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    freopen("SOMAYMAN.inp", "r", stdin);
    freopen("SOMAYMAN.out", "w", stdout);

    for(int i = 1; i < MAXN; i ++)
    {
        f[i] = 1;
    }

    for(int i = 2; i < MAXN; i ++)
    {
        if(f[i] == 1)
        {
            for(int j = i; j < MAXN; j += i)
            {
                f[j] *= i;
            }
        }
    }

    cin >> n;

    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        cnt[f[a[i]]] ++;
    }

    long long res = 0;

    for (int i = 1; i < MAXN; i ++)
    {
        res += (long long)cnt[i] * (cnt[i] - 1) / 2;
    }

    cout << res ;
}
