#include <fstream>

using namespace std;

ifstream in("pairs.in");
ofstream out("pairs.out");

int n;

bool notprim[1005];
int p[169], np;
int v[8];
int nrp[1000005];
bool semn[1000005];

int main()
{
    in >> n;

    notprim[1] = 1;
    for(int i = 2; 2 * i <= 1000; i++)
        notprim[2 * i] = 1;
    for(int i = 3; i * 3 <= 1000; i += 2)
        for(int j = 3; i * j <= 1000; j += 2)
            notprim[i * j] = 1;
    for(int i = 1; i <= 1000; i++)
        if(notprim[i] == 0)
            p[++np] = i;

    for(int i = 1; i <= n; i++)
    {
        int x;
        in >> x;
        int nr = 0;
        for(int i = 1; i <= np && p[i] * p[i] <= x; i++)
            if(x % p[i] == 0)
            {
                v[nr++] = p[i];
                while(x % p[i] == 0)
                    x /= p[i];
            }
        if(x != 1)
            v[nr++] = x;

        for(int i = 0; i < (1 << nr); i++)
        {
            int prod = 1;
            int smn = -1;
            for(int j = 0; j < nr; j++)
                if(i & (1 << j))
                {
                    smn = -smn;
                    prod *= v[j];
                }

            if(prod != 1)
            {
                if(smn == 1)
                    semn[prod] = 1;
                else
                    semn[prod] = 0;
                nrp[prod]++;
            }
        }
    }

    long long rez = 0;
    for(int i = 2; i <= 15; i++)
    {
        if(semn[i])
            rez += (long long)nrp[i] * (nrp[i] - 1) / 2;
        else
            rez -= (long long)nrp[i] * (nrp[i] - 1) / 2;
    }
    out << (long long)n * (n - 1) / 2 - rez << '\n';
    return 0;
}