#include <bits/stdc++.h>
///N=100000
///M=1000000
using namespace std;
///
typedef long long ll;
///
ll n, m, i, j, k, sol;
ll cnt[1000001], val[100001];
bitset<1001> ciur;
bitset<1000001> check;
vector<ll> primes, divone[100002];
///
void read();
void solve();
void write();
void buildCiur();
void bkt(ll last, ll val, ll mp, bool what, bool get);
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("pairs.in", "r", stdin);
    scanf("%lld", &n);
    for(i=1; i<=n; ++i) scanf("%lld", &val[i]);
    fclose(stdin);
}
void solve(){
    buildCiur();
    for(i=1; i<=n; ++i){
        ll div=val[i];
        for(j=0; j<primes.size(); ++j){
            ll jj=primes[j];
            if(1LL*jj*jj>div) break;
            if(!(div%jj)){
                divone[i].push_back(jj);
                if(!check[divone[i][divone[i].size()-1]]){
                    check[divone[i][divone[i].size()-1]]=true;
                    divone[n+1].push_back(divone[i][divone[i].size()-1]);
                }
                while(!(div%jj)) div/=jj;
            }
        }
        if(div>1) {
            divone[i].push_back(div);
            if(!check[divone[i][divone[i].size()-1]]){
                check[divone[i][divone[i].size()-1]]=true;
                divone[n+1].push_back(divone[i][divone[i].size()-1]);
            }
        }
    }
    for(i=1; i<=n; ++i) bkt(-1LL, 1LL, 0, false, false);
    bkt(-1LL, 1LL, 0, true, false);
}
void write(){
    freopen("pairs.out", "w", stdout);
    printf("%lld", n*(n-1)/2-sol);
    fclose(stdout);
}
void buildCiur(){
    for(i=2; i<=1000; ++i){
        if(ciur[i]) continue;
        primes.push_back(i);
        for(j=2*i; j<=1000; j+=i) ciur[j]=true;
    }
}
void bkt(ll last, ll val, ll mp, bool what, bool get){
    if(!what && mp && get) ++cnt[val];
    else if(what && mp && get){
        int mult=((mp&1)?1:-1);
        sol=sol+1LL*mult*cnt[val]*(cnt[val]-1)/2;
    }
    if(last==divone[i].size()-1) return;
    bkt(last+1, val, mp, what, false);
    bkt(last+1, val*divone[i][last+1], mp+1, what, true);
}