#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define re register
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define fi first
#define se second
using namespace std;
ll read(){
	ll k=0,flag=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')flag=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		k=(k<<1)+(k<<3)+(c^48);
		c=getchar();
	}
	return k*flag;
}
void print(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)print(x/10);
    putchar(x%10+'0');
    return ;
}
const int N=2e5+10;
int n,cnt,p[N],x[N];
ll ans,cnt0;
ull h[N];
bool vis[N];
unordered_map<ull,ll>mp;
unordered_map<ull,bool>flag;
int main(){
    cin>>n;
    vis[1]=1;
    for(int i=2;i<=(int)2e5;++i){
        if(!vis[i])p[++cnt]=i;
        for(int j=1;j<=cnt&&i*p[j]<=(int)2e5;++j){
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
    for(int i=1;i<=n;++i){
        x[i]=read();
        if(!x[i]){
            ++cnt0;
            continue;
        }
        int t=x[i];
        ull hash=0;
        if(h[x[i]]){
            ++mp[h[x[i]]];
            continue;
        }
        for(int j=1;j<=cnt;++j){
            if(p[j]>t)break;
            if(t&&t%p[j]==0){
                int num=0;
                while(t&&t%p[j]==0){
                    t/=p[j];
                    ++num;
                }
                if(num&1){
                    hash*=(ull)13331;
                    hash+=(ull)p[j];
                }
            }
        }
        ++mp[hash];
        h[x[i]]=hash;
    }
    ans+=cnt0*(n-1);
    for(int i=1;i<=n;++i){
        if(flag[h[x[i]]])continue;
        ll k=mp[h[x[i]]];
        flag[h[x[i]]]=1;
        ans+=k*(k-1)/2;
    }
    cout<<ans;
	return 0;
}