#include <cstdio>
#include <vector>
#define INF "pairs.in"
#define OUF "pairs.out"
#define NMAX 100002
#define PMAX 1024
using namespace std;

struct nod
{
	int nd,rez;
	long long b[4];
	void fl() { b[0]=b[1]=b[2]=b[3]=0;}
}v[NMAX];

short id[PMAX]={0};

void erat()
{
	short i,j;
	for(i=2;i<PMAX;++i)
		if(!id[i])
		{
			for(j=2*i;j<PMAX;j+=i) id[j]=1;
		}
}

int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	int i,j,n,x,sz,aux;
	vector<int> div;
	long long sol;
	nod ax;

	j=0;
	erat();
	for(i=2;i<PMAX;++i) if(!id[i]) { div.push_back(i);id[i]=j;++j;}
	sz=div.size();

	fscanf(in,"%d",&n);
	sol=0;

	for(i=1;i<=n;++i)
	{
		fscanf(in,"%d",&x);
		v[i].nd=0;v[i].fl();

		for(j=0;j<sz&&div[j]<=x;++j)
		if(x%div[j]==0)
		{
			aux=id[div[j]];
			v[i].b[aux/64]|=(1<<(aux%64));
//			printf("%d ",aux);
			
			while(x%div[j]==0){ ++v[i].nd;x/=div[j];}
		}

		v[i].rez=x;
		if(x!=1) ++v[i].nd;
//		printf("%lld \n",v[i].b[0]);
		
	}

	for(i=1;i<n;++i)
		for(j=i+1;j<=n;++j)
		if(v[i].rez==v[j].rez&&((v[i].b[0]&v[j].b[0])|(v[i].b[1]&v[j].b[1])|(v[i].b[2]&v[j].b[2])|(v[i].b[3]&v[j].b[3]))) ;
		else
		{
			++sol;
		//	printf("%d %d\n",i,j);
		}

	fprintf(out,"%lld",sol);
	fclose(in);fclose(out);
	return 0;
}