#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int n;
int val[N], vis[N];
vector<int> g[N];
inline int Mysqrt(int x) {
    int t = sqrt(x);
    while (t * t < x) ++t;
    while (t * t > x) --t;
    return t;
}
signed main() {
    for (int i = 1; i < N; ++i) val[i] = i;
    for (int i = 2; i < N; ++i) {
        int t = i * i;
        if (t >= N) break;
        for (int j = t; j < N; j += t) {
            while (val[j] % t == 0) val[j] /= t;
        }
    }
    scanf("%lld", &n);
    for (int i = 1, x; i <= n; ++i) {
        scanf("%lld", &x);
        vis[x] = 1;
        g[val[x]].push_back(x);
    }
    int ans = 0;
    for (int v = 1; v < N; ++v) {
        for (auto x : g[v])
            for (auto y : g[v]) {
                if (y >= x) break;
                ans += vis[Mysqrt(x * y)];
            }
    }
    printf("%lld\n", ans);
    return 0;
}