#include<cstdio>

int i,j,n,a[1024],aux[1024],cmdc[1024][1024];

int cmmdc(int a,int b)
{
	if(!b) return a;
	
	return cmmdc(b,a%b);
}

int main()
{
	freopen("indep.in","r",stdin);
	freopen("indep.out","w",stdout);
	
	scanf("%d",&n);
	
	for(i=1;i<=1000;++i)
		for(j=i+1;j<=1000;++j)
			cmdc[i][j]=cmdc[j][i]=cmmdc(i,j);
	
	for(i=1;i<=n;++i)
	{
		int x=0;
		scanf("%d",&x);
		
		aux[x]+=1;
		
		for(j=1;j<=1000;++j) 
			if(a[j])
			{
				int cm=cmdc[j][x];
				aux[cm]+=a[j];
			}
		for(j=1;j<=1000;++j) 
			if(aux[j]) 
			{
				a[j]+=aux[j];
				aux[j]=0;
			}
	}
	
	printf("%d\n",a[1]);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}