#include<stdio.h>
#include<vector>

using namespace std;

#define NMAX 100000

void getA(int x);

int N, V[NMAX], L[NMAX * 11], nr[NMAX * 11];
char P[1024];
vector<int> A, p;

int main()
{
	int i, j, z, ok;

	freopen("pairs.in", "r", stdin);
	freopen("pairs.out", "w", stdout);

	scanf("%d", &N);
	
	for(i = 2; i <= 1000; i++)
	for(j = 2; j * i <= 1000; j++)
		P[j * i] = 1;

	for(i = 2; i <= 1000; i++)
		if(!P[i]) 
			p.push_back(i);

	for(i = 0; i < N; i++)
	{
		scanf("%d", V + i);
		getA(V[i]);
		for(j = 0; j < (1 << ((int)A.size())); j++)
		{
			ok = 1;
			for(z = 0; z < A.size(); z++)
				if(j & (1 << z))
					ok *= A[z];
			if(ok > 1)
			L[ok]++;
		}
	}
	
	long long rez = (long long) N * (N - 1);
	rez >>= 1;
	for(i = 2; i <= 1000000; i++)
	{
		if(!nr[i])
			for(j = 2; j * i <= 1000000; j++)
				nr[j * i]++;

		if(nr[i] == 0 || nr[i] % 2 == 1)
		rez -= ((long long)L[i] * (L[i] - 1)) / 2;
		else
		rez += ((long long)L[i] * (L[i] - 1)) / 2;
	}
	
	printf("%lld\n", rez);
	return 0;
}

void getA(int x)
{
	int i;

	A.clear();

	for(i = 0; x > 1 && i < p.size(); i++)
		if(x % p[i] == 0)
		{
			A.push_back(p[i]);
			while(x % p[i] == 0)
				x /= p[i];
		}
	if(x > 1)
		A.push_back(x);
}