Untitled

#pragma GCC optimize("O2,no-stack-protector,unroll-loops")
#define ll long long
#define pb push_back
#define ipar(arr, n) vector<ll> arr(n); for(int i=0;i<n;i++) cin>>arr[i];
#include <cmath>
#include <bits/stdc++.h>
#define pii pair<int, int>;
#define pll pair<ll, ll>;
using namespace std;

void facto(ll n,vector<ll>&primep){
    while(n%2==0){ 
        n/=2;
        primep[2]++;
    }
    for(ll i=3;i<=sqrt(n);i+=2){
        while(n%i==0){
            n/=i;
            primep[i]++;
        }
    }
    if(n>2) primep[n]++;
}

void solve(){
    
    /*******************preprocessing******************/
    const ll N = 200000;
    vector<ll>sqfree(N+1); // sqfree[i] , i is the number not a index
    iota(sqfree.begin(),sqfree.end(),0);

    for(ll p=2;p<=N;p++){
        for(ll c=p;c<=N;c+=p){
            ll &cur=sqfree[c];
            ll cnt=0;
            while(cur%p ==0){
                cnt++;
                cur/=p;
            }
            if(cnt%2==1){ // incase the number at sqfree[c] had odd no of prime factors then one prime factor stays in the sqf rep of cur 
                cur*=p;
            }
        }
    }

    ll n;cin>>n;
    unordered_map<ll,ll>freq;

    ll z=0;
    for(ll i=0;i<n;i++){
        ll inp; cin>>inp;
        if(inp==0) {z++; continue;}

        inp=sqfree[inp];
        freq[inp]++;
    }
    ll ans=z*(n-z) + z*(z-1)/2; //1 zero 2 zero
    for(auto x:freq){
        ll no=x.first;
        ll f=x.second;
        ans+=f*(f-1)/2;
    }
    cout<<ans<<"\n";
}


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
	//cin>>t;
	while(t--) solve();
    //cout<<"ok";
}