#include<iostream.h>
#include<fstream.h>
int

void prim()
    { r=sqrt((double)max);
      for(i=0;i<=r;i++)
	    j=i*i;
	    for(j<=max)
		     {e[j]=1;j=j+i;}
      for(i=0;i<r;i++)
	       if(e[i]==0) p[++j]=i;
    }
void multipli()
     { for (i=2;i<max;i++)
	    {r=max/i;
	     for(j=1;j<r;j++)
		 if(a[i*j]==1) x[i]++;
	    }







void main()
{
ifstream h("pairs.in");
ofstream g("pairs.out");
h>>n;h>>x;max=x;
for(i=1;i<n;i++)
      {a[x]=1;
       if(x>max) max=x;
       h>>x;
       }
sol=n(n-1)/2;
dif=0;
for(i=2;i<max;i++)
     { if(x[i]!=1) { r=i;nr=0;
		     for(j=0;p[j]<sqrt((double r))
			     {if(r%p[j]==0) {nr++;
					     r/=p[j];
					     if(r%p[j]==0) {nr=-1;break;}
					     }
		     if(nr!=-1) { nr++;
				  if(nr%2==0)