#include<stdio.h>
int long d,nr,i,j,n,s[500],k1;
int long k;
int long cmmdc(int long a,int long b)
{return !b?a:cmmdc(b,a%b);}


int main()
{freopen("indep.in","r",stdin);
 scanf("%d",&n);
 for(i=1;i<=n;i++)
  scanf("%d",&s[i]);
 for(i=1;i<=n;i++)
  {nr=i-1;
  for(j=i+1;j<=n;j++)
   {d=cmmdc(s[i],s[j]);
	if(d==1)
	 {k+=1<<n-2-nr;
	  nr++;
	  }
	}
   }
 k1=k;k=0;
 for(i=1;i<1<<n;i++)
  {for(j=0,nr=0;j<n;j++)
	 if(i&1<<j)
	   {nr++;
		if(nr==1)
		   d=s[j+1];
		else
		   d=cmmdc(s[j+1],d);
		}
   if(d==1)
	 k++;
   }




 freopen("indep.out","w",stdout);
 printf("%ld",k);
 fclose(stdout);
 return 0;
 }