#include <bits/stdc++.h>
#define VMAX 1000001
#define NMAX 100001
#define SQRT 1000
#define DIV 7
using namespace std;

int n;
int m[NMAX]; ///multimea citita

bitset<SQRT/2> ciur;
vector<int> prime;
void eratostene() ///calculeaza ciurul lui eratostene
{
     for(int i=3; i*i<SQRT; i+=2)
     {
         if(ciur[i/2]==0)
         {
            for(int j=i*i; j<SQRT; j+=2*i)
                ciur[j/2]=1;
         }
     }
     prime.push_back(2);
     for(int i=3; i<SQRT; i+=2)
     {
         if(ciur[i/2]==0)
            prime.push_back(i);
     }
}

int descompunere(int i) ///descompune numarul m[i] in factori primi
{
    int nr=m[i], prod_div=1; ///prod_div reprezinta produsul divizorilor primi ai lui nr
    for(int d=0; d<prime.size() && prime[d]*prime[d]<=nr; d++)
    {
        if(nr%prime[d]==0)
        {
            prod_div*=prime[d];

            while(nr%prime[d]==0)
                nr/=prime[d];
        }
    }
    if(nr>1)
    {
        prod_div*=nr;
    }
    return prod_div;
}

int frecv_produs[VMAX]; ///salvam de cate ori apare fiecare produs de numere prime (la puterea 1) ca divizor al unui numar din m
bitset<VMAX> paritate_nrdiv; ///paritatea numarului de divizori primi al fiecarui numar de la 1 la 1 000 000

void precalculare_paritate() ///precalculeaza paritatea numarului de divizori primi al fiecarui numar
{
    bitset<VMAX/2> este_prim; ///salvam pentru fiecare numar daca este prim sau nu

    for(int i=2; i<VMAX; i+=2)
        paritate_nrdiv[i]=(~paritate_nrdiv[i]);

    for(int i=3; i*i<VMAX; i+=2)
    {
         if(este_prim[i/2]==0)
        {
            for(int j=i; j<VMAX; j+=i)
            {
                este_prim[j/2]=1;
                paritate_nrdiv[j]=(~paritate_nrdiv[j]); ///schimbam paritatea numarului de divizori
            }
        }
    }
}

int main()
{
    ifstream cin("pairs.in");
    ofstream cout("pairs.out");
    eratostene();
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> m[i];
        int prod_div=descompunere(i); ///descompunem in factori primi numarul m[i] si salvam produsul divizorilor primi
        frecv_produs[prod_div]++;
    }

    for(int i=1; i<VMAX; i++) ///la frecventa fiecarui produs adunam frecventele tuturor multiplilor sai
    {
        for(int j=i*2; j<VMAX; j+=i)
            frecv_produs[i]+=frecv_produs[j];
    }

    precalculare_paritate();
    long long nr_perechi=(long long)n*(n-1)/2;
    for(int i=2; i<VMAX; i++)
    {
        if(paritate_nrdiv[i]==1) ///daca numarul de divizori primi este impar
            nr_perechi-=(long long)frecv_produs[i]*(frecv_produs[i]-1)/2; ///scadem numarul de perechi divizibile cu i

        else ///daca numarul de divizori primi este par
            nr_perechi+=(long long)frecv_produs[i]*(frecv_produs[i]-1)/2; ///adunam numarul de perechi divizibile cu i
    }
    cout << nr_perechi;

    return 0;
}