#include <iostream>
#include<fstream>
#include<cmath>
using namespace std;
bool used[10],nprime[1005];
int v[10],a[10],x,i,n,fix,c,k,ap[1000005],p,prime[1005],ind,j;
long long tot;
void precalcprimes()
{
    k=0;fix=floor(sqrt(x))+1;
    ind=1;
    while(x!=1)
    {
        c=prime[ind];
        if(x%c==0)
        {
            k++;
            a[k]=c;
            while(x%c==0)
                x/=c;
        }
        if(c>fix&&x!=1) {k++;a[k]=x;x=1;}
        ind++;
    }
}
void bk(int xy)
{
    if(xy>c)
    {
        if(c%2==0) {tot=tot+(ap[p]);}
        else {tot=tot-(ap[p]);}
        ap[p]++;
    }
    else
    {
        for(int j=v[xy-1]+1;j<=k;j++)
        {
            if(!used[j])
            {
                v[xy]=j;
                used[j]=1;
                p*=a[j];
                bk(xy+1);
                used[j]=0;
                p/=a[j];
            }
        }
    }
}
int main()
{
    ifstream f("pairs.in");
    ofstream g("pairs.out");
    f>>n;
    p=1;
    tot=(1LL)*n*(n-1)/2;
    for(i=2;i<=1000;i++)
        if(nprime[i]==0)
    {
        k++;
        prime[k]=i;
        for(j=2*i;j<=1000;j+=i)
            nprime[j]=1;
    }
    for(i=1;i<=n;i++)
    {
        f>>x;
        precalcprimes();
     for(c=1;c<=k;c++)
        bk(1);
    }
    g<<tot;
    return 0;
}