#include <cstdio>
const int valmax = 1000001;

FILE *f = fopen("pairs.in","r");
FILE *g = fopen("pairs.out","w");
int n, m;
int r[valmax],e[valmax], p[valmax];
char w[valmax];

bool isin(int val)
{
    int i;
    for (i = 0; i< m ; i++)
        if (val == e[i])
            return true;
    return false;
}
int main()
{
    int i, j, o;
    fscanf(f,"%d",&n);
    for (i = 2; i < valmax; i++)
        if (r[i] == 0) {
            r[i] = i;
            w[i] = 1;
            j= 2 * i;
            while (j < valmax) {
                if (r[j] == 0)
                    r[j] = i;
                w[j] ^= 1;
                j += i;
            }
        }
    for (i = 1; i<=n ; i++) {
        int x, y;
        fscanf(f,"%d",&x);
        m = 0;
        while (x!=1) {
            if (!isin(r[x]))
                e[m++] = r[x];
            x/= r[x];
        }
        for (j = 1; j < (1<<m); j++) {
            y = 1;
            for (o = 0; o < m ; o++)
                if (j & (1<<o))
                    y *= e[o];
            if (y!=1)
                p[y] ++;
        }
    }

    long long nop = (1LL * n * (n - 1))/2;
    for (i = 2 ; i < valmax ; i++)
        if (p[ i ] != 0) {
            if (w[i] % 2 == 1)
                nop -= p[i] * (p[i] - 1) / 2;
            else
                nop += p[i] * (p[i] - 1) / 2;
        }
    fprintf(g,"%lld",nop);
    return 0;
}