#include <iostream>
#include<fstream>
#include<cmath>
using namespace std;
bool used[10],gg[1000005];
int v[10],a[10],x,i,n,fix,c,k,ap[1000005],p;
long long tot;
void precalcprimes()
{
    k=0;fix=floor(sqrt(x))+1;
    c=2;
    while(x!=1)
    {
        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;}
        c++;
    }
}
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=1;i<=n;i++)
    {
        f>>x;
        precalcprimes();
     for(c=1;c<=k;c++)
        bk(1);
    }
    g<<tot;
    return 0;
}