#include <stdio.h>
#include <string.h>

#define NMAX 100100
#define MMAX 1000001

#define BIGINT long long //__int64 // long long
#define fmt "%lld"//"%I64d" // "%lld"

#define NPRIMES 100000
#define MAXPRIMES 1001
#define MAXP 10

char prim[MMAX], nprimes[MMAX];
int cnt[MMAX], prime[MAXPRIMES], p[MAXP], bit[MAXP], np;
BIGINT npairs, vaux1, vaux2;
int i, j, k, N, x, y, z, numprimes;

int main()
{
	// generate primes (cu ciur)

	for (i = 2; i < MMAX; i++)
		prim[i] = 1,
		nprimes[i] = 0,
		cnt[i] = 0;

	for (i = 2; i < MMAX; i++)
		if (prim[i])
		{
			nprimes[i] = 1;

			for (j = 2 * i; j < MMAX; j += i)
				prim[j] = 0,
				nprimes[j]++;
		}

	numprimes = 0;

	for (i = 2; i < MAXPRIMES; i++)
		if (prim[i])
		{
			prime[numprimes] = i;
			numprimes++;
		}

	bit[0] = 1;

	for (i = 1; i < MAXP; i++)
		bit[i] = bit[i - 1] << 1;

	freopen("pairs.in", "r", stdin);

	scanf("%d", &N);

	for (i = 1; i <= N; i++)
	{
		scanf("%d", &x);

		if (prim[x])
			cnt[x]++;
		else
		{
			np = 0;

			for (y = x, k = 0; k < numprimes; k++)
			{
				j = prime[k];

				if (j * j > x)
					break;

				if (y % j == 0)
				{
					p[np++] = j;

					while (y % j == 0)
						y /= j;
				}
			}

			if (y > 1)
				p[np++] = y;

			z = 1 << np;

			for (y = 1; y < z; y++)
			{
				x = 1;
			
				for (k = 0; k < np; k++)
					if (y & bit[k])
						x *= p[k];

				cnt[x]++;
			}
		}
	}

	vaux1 = N;
	npairs = (vaux1 * (vaux1 - 1)) / 2;

	for (i = 2; i < MMAX; i++)
		if (cnt[i] > 1)
		{
			vaux1 = cnt[i];
			vaux1 = (vaux1 * (vaux1 - 1)) / 2;

			if (nprimes[i] & 1)
				npairs -= vaux1;
			else
				npairs += vaux1;
		}

	freopen("pairs.out", "w", stdout);
	printf(fmt, npairs);
	printf("\n");

	return 0;
}