#include <stdio.h>
int nr1,l,i,j,k,n,max;
int a[501];
int din[2][1001][31];
void add(int p, int q,int r, int t)
{
	 int i,tr=0;
	 for (i=30; i>=1; i--)
	 {
		 din[p][q][i]+=din[r][t][i]+tr;
		 tr=din[p][q][i]/100000000;
		 din[p][q][i]%=100000000;
	 }
}
int cmmdc(int x, int y)
{
	int a=x,b=y,r;

	while (a%b!=0)
	{
		  r=a%b;
		  a=b;
		  b=r;
	}
	return b;
}
int main()
{

	freopen("indep.in","r",stdin);
	freopen("indep.out","w",stdout);

	scanf("%d",&n);
	max=0;nr1=0;
	for (i=1; i<=n; i++)
	{
		 scanf("%d",&a[i]);
		 if (a[i]>max) max=a[i];
		 if (a[i]==1) nr1++;
	}
	l=0;
	for (i=0; i<=n-1; i++)
	{
		l=1-l;
		din[l][a[i+1]][30]++;
		if (l==1)
		for (j=1; j<=max; j++)
		{
			add(1,j,0,j);
			add(1,cmmdc(j,a[i+1]),0,j);
			int o;
			for (o=1; o<=30; o++)
				din[0][j][o]=0;
		}
		else
		for (j=1; j<=max; j++)
		{
			add(0,j,1,j);
			add(0,cmmdc(j,a[i+1]),1,j);
			int o;
			for (o=1; o<=30; o++)
				din[1][j][o]=0;
		}
	}
    din[l][1][30]-=nr1;
    for (i=30; i>=1; i--)
    if (din[l][1][i]<0)
    {
       din[l][1][i]+=100000000;
       din[l][1][i-1]--;
    }
	j=0;
	for (i=1; i<=30; i++)
		if (din[l][1][i]!=0)
		{
		   for (j=i; j<=30; j++)
			   printf("%d",din[l][1][j]);
		   printf("\n");
		   return 0;
		}
	printf("0\n");
	return 0;
}