#include <cstdio>
using namespace std;
int mem[1001][1001],i,j,k,t,a[1001][202],n,x,c=100000000,r;
int cmmdc(int a,int b)
{
	if(mem[a][b]==0){
		if(b==0){mem[a][b]=a;mem[b][a]=a;}
		else{mem[a][b]=cmmdc(b,a%b);mem[b][a]=mem[a][b];}
					}
	return mem[a][b];
}

int main()
{
	freopen("indep.in","r",stdin);
	freopen("indep.out","w",stdout);
	scanf("%ld",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		for(j=1;j<=1000;j++){
			t=cmmdc(x,j);
			k=200;r=0;
			while((a[t][k])||(a[j][k])||(r)){
				a[t][k]+=a[j][k]+r;
				r=a[t][k]/c;
				a[t][k]%=c;
				k--;
											}
							}
		a[x][200]+=1;
					 }
	x=0;
	for(k=1;k<=200;k++){if((x)||(a[1][k])){printf("%d",a[1][k]);x=1;}}
	if(x==0){printf("0");}
return 0;
}