#include "fstream.h"
#include "conio.h"
#define N 500

ifstream f("indep.in");
ofstream g("indep.out");
int div(int a,int b)
{
   int r,d;
   if(a==0)
   {
      if(b!=0)
	d=b;
   }

   else
     if(b==0)
	d=a;
   if(a!=0&&b!=0)
   {
   r=a%b;
   while(r)
   {
     a=b;
     b=r;
     r=a%b;
   }
   d=b;
   }
return d;
}
int main()
{int n,i,v[N],a[N],s[N],ss,k,d,nr=0,x,r,dd;
f>>n;
clrscr();
for(i=1;i<=n;i++)
{
   f>>a[i];
   v[i]=0;
}
f.close();
ss=0;
while(ss!=n)
{
  i=n;
  while(v[i]==1)
  {
      v[i]=0;
      i--;
  }
  v[i]=1;
  k=0;
  ss=0;
  for(i=1;i<=n;i++)
     if(v[i]==1)
     {
	ss+=v[i];
	k++;
	s[k]=a[i];
     }
  dd=s[1];
  for(x=2;x<=k;x++)
     dd=div(dd,s[2]);
  if(dd==1)
     nr++;
}
g<<nr;
g.close();
return 0;
}