#include<stdio.h>
#include<math.h>
FILE*f=fopen("pairs.in","r");
FILE*g=fopen("pairs.out","w");
int j,x,y,i,n,sol,z,v[100001],p[200],w[10],a[1000001],k;
char o[1001],b[1000001],s[10];

void tipar(int x){
	int sol=1;
	int nr=0;
	for(int dd=1;dd<=z;++dd){
		if(s[dd]==1){
			sol*=w[dd];
			nr++;
		}
	}
	a[sol]++;
	b[sol]=nr%2;
	if(b[sol]==0)
		b[sol]=-1;
}
void back(int x){
	if(x>z)
		tipar(z);
	else
		for(int ff=0;ff<=1;++ff){
			s[x]=ff;
			back(x+1);
		}
}
int main(){
	fscanf(f,"%d",&n);
	for(int i=1;i<=n;++i)
		fscanf(f,"%d",&v[i]);
	
	for(int i=2;i<=1000;++i)
		if(o[i]==0){
			p[++k]=i;
			for(int j=2*i;j<=1000;j+=i)
				o[j]=1;
		}
	for(int ii=1;ii<=n;++ii){
		z=0;
		x=v[ii];
		y=sqrt(x);
		for(int j=1;j<k&&x>1&&p[j]<=y;++j){
			if(x%p[j]==0){
				while(x%p[j]==0)
					x/=p[j];
				w[++z]=p[j];
			}
			
		}
		if(x>y)
			w[++z]=x;
		back(1);
		
	}
	
	for(int i=2;i<=1000000;++i)
		sol+=b[i]*a[i]*(a[i]-1)/2;
	
	fprintf(g,"%d",n*(n-1)/2-sol);
	
	fclose(g);
	fclose(f);
	return 0;
}