#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#define MAXN 100005
#define MAXM 1000005
#define MAXPRIM 80000
FILE *f=fopen("pairs.in","r"), *g=fopen("pairs.out","w");

using namespace std;

bool viz[MAXM];
int N, n, x, K;
int Ciur[MAXPRIM], LCiur, F[10], LF, R[MAXM];
bool bk[10];
long long Rfinal;

    // NrPre[i] = Numarul de termeni i, descompusi deja in Pre
    // LF = factorii unui numar

vector <int> Lista[MAXM];
vector <int> NrFactori[MAXM];
int NrLista[MAXM];

void CreareCiur(){
int i, j;

    LCiur = 0;
    viz[1] = 1;
    for(i=2;i<=MAXM-5;i++)
        if( viz[i] == 0 ){
            Ciur[ ++LCiur ] = i;
            for(j=i+i;j<=MAXM-5;j+=i)
                viz[j] = 1;
        }
}

void Pune(){
int i, nr;

    nr = 1;
    for( i = 1; i <= LF; i++ )
        if( bk[i] == 1 )
            nr *= F[i];

    if( nr != 1 )
        Lista[K].push_back( nr );

}

void back( int k ){

    if( k > LF )
        Pune();
    else
        for( int i = 0; i <= 1; i++ ){
            bk[k] = i;
            back(k+1);
        }

}

void Rezolva( int nr ){
int i, j, rad, prim, NOUnr;

    rad = sqrt( nr );
    NOUnr = 1;

    LF = 0;
    for(i=1;i<=LCiur;i++){

        prim = Ciur[i];

        if( prim > rad )
            break;

        if( nr % prim == 0 ){
            NOUnr  *= prim;
            F[++LF] = prim;
            while( nr % prim == 0 )
                nr /= prim;
        }

    }   if( viz[nr] == 0 ){
            F[++LF] = nr;
            NOUnr  *= nr;
        }

    if( NrLista[ NOUnr ] == 0 ){

        K = NOUnr;
        back(1);
        NrFactori[ NOUnr ].push_back( LF );

    }

    NrLista[ NOUnr ] ++;

}

int main(){

    CreareCiur();
    fscanf(f,"%d\n",&N);
    for(int i=1;i<=N;i++){
        fscanf(f,"%d\n",&x);
        Rezolva(x);
    }

    for(int i=1;i<=1000000;i++)
        if( NrLista[i] != 0 )
            for(int j=0;j<Lista[i].size();j++ )
                R[ Lista[i][j] ] += NrLista[i];


    Rfinal = 1LL * N * (N-1) / 2;
    for(int i=1;i<=1000000;i++)
        if( R[i] != 0 ){
            if( NrFactori[i][0] %2 == 1 )
                Rfinal -= 1LL * R[i] * ( R[i] - 1 ) / 2;
            else
                Rfinal += 1LL * R[i] * ( R[i] - 1 ) / 2;
        }
    fprintf(g,"%lld\n",Rfinal);

return 0;
}