#include <stdio.h>
#include <stdlib.h>
#define FIN "pairs.in"
#define FOUT "pairs.out"
#define N 100100
#define M 1000100
#define bool char
#define true 1
#define false 0
bool set[M];/*
int what_is(int x,int b){ 
     return ((x & (1 << (b-1))) != 0);
}
inline void set_byte(v[i]){
	int x,y;
	x=v[i]/8;
	y=v[i]%8;
	set[x]=k | (1 << (s[i].type-1));
}*/
int n;
char x[M];
int nrd[M];
inline void set_byte(int x){
	set[x]=(set[x]>>1)*2+1;
}
inline void set_ciur(int x){
	set[x]=(set[x]/4)*4+2+set[x]%2;
}
inline char is_set_ciur(int x){
	return set[x]%4>>1;
}
inline char is_set_byte(int x){
	return set[x]%2;
}
void scan(void){
	char s[8];
	int i,j,k=0;
	freopen(FIN,"r",stdin);
	freopen(FOUT,"w",stdout);
	gets(s);
	for (i=0;s[i]>='0'&& s[i]<='9';++i)
		n=n*10+s[i]-'0';
	for (j=1;j<=n;++j){
		gets(s);k=0;
		for(i=0;s[i]>='0'&& s[i]<='9';++i)
			k=k*10+s[i]-'0';
		set_byte(k);
	}
}
void ciur(void){
	int i,j,k;
	++x[2];
	for (i=4;i<M;i+=2){
		++x[i];
		set_ciur(i);
	}
	for (i=3;i<=M;i+=2)
		if (!is_set_ciur(i)){
			++x[i];
			for (j=i+i;j<=M;j+=i){
				set_ciur(j);
				++x[j];
			}
		}
	for (i=2;i*i<=M;++i){
		k=i*i;
		for (j=k;j<=M;j+=k)
			x[j]=-1;
	}
	for (i=2;i<=M;++i)
		for (j=i;j<=M;j+=i)
			if (is_set_byte(j))
				++nrd[i];
	//for (i=1;i<=20;++i)
		//printf("%d ",is_set_ciur(i));
	//printf("\n");
	//for (i=1;i<=20;++i)
		//printf("%d ",x[i]);
	//printf("\n");
	//for (i=1;i<=20;++i)
		//printf("%d ",nrd[i]);
}
inline long long comb(int x){
	if(x<2)
		return 0;
	return (long long)x*(long long)(x-1)>>1;
}
void solve(void){
	int i;
	long long all,s=0;
	all=comb(n);
	//printf("%d\n",all);
	ciur();
	for (i=2;i<=M;++i){
		if (x[i]!=-1){
			if (x[i]%2==1)
				s+=comb(nrd[i]);
			else
				s-=comb(nrd[i]);
		}
	}
	//printf("%lld\n",s);
	//printf("%lld\n",comb(3));
	printf("%lld\n",all-s);
}
void print(void){
	exit(0);
}
int main(void){
	scan();
	solve();
	print();
}