#include<stdio.h>
#define Nm (1<<17)
#define Vm (1<<20)
int M[Nm],P[Vm],Nr[Vm],n;
long long ans;

void read()
{
    int i;

    freopen("pairs.in","r",stdin);
    scanf("%d",&n);
    for(i=0;i<n;++i)
        scanf("%d",M+i);
}

void solve()
{
    int Bits[128],Poz[128],Prod[128],F[10],i,j,k,x;

    for(i=2;i<=1000000;i+=2)
        P[i]=2;

    for(i=3;i<1000;i+=2)
        if(!P[i])
            for(j=i*i;j<=1000000;j+=i<<1)
                if(!P[j])
                    P[j]=i;

    for(i=3;i<1000000;i+=2)
        if(!P[i])
            P[i]=i;

    Bits[0]=0; Bits[1]=1; Poz[1]=0;
    for(i=2;i<128;++i)
    {
        Bits[i]=Bits[i>>1]+(i&1);
        for(j=0;;++j)
            if(i&1<<j)
            {
                Poz[i]=j;
                break;
            }
    }
    Prod[0]=1;

    for(i=0;i<n;++i)
    {
        x=M[i]; k=0;
        while(x>1)
        {
            if(!k || P[x]>F[k-1])
                F[k++]=P[x];
            x/=P[x];
        }

        for(j=1;j<1<<k;++j)
        {
            Prod[j]=Prod[j^1<<Poz[j]]*F[Poz[j]];
            ++Nr[Prod[j]];
        }
    }

    for(i=0;i<n;++i)
    {
        x=M[i]; k=0;
        while(x>1)
        {
            if(!k || P[x]>F[k-1])
                F[k++]=P[x];
            x/=P[x];
        }

        for(j=1;j<1<<k;++j)
        {
            Prod[j]=Prod[j^1<<Poz[j]]*F[Poz[j]];
            ans+=Nr[Prod[j]]*(Bits[j]&1?1:-1);
        }
    }
    ans=((long long)n*n-ans)>>1;
}

void write()
{
    freopen("pairs.out","w",stdout);
    printf("%lld\n",ans);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}