#include <cstdio>
#include <cstring>
#define NMAX 1001
#define max(a,b) (a>b?a:b)
#define MOD 10000000

using namespace std;

int n,M,i,c,j;
int a[NMAX];
 int vec1[2*NMAX];
int mat[NMAX][NMAX];
 int cnt[NMAX][2*NMAX];

int cmmdc(int a,int b)
{
    int r=0;
    while(a>0)
    {
        r=b%a;
        b=a;
        a=r;
    }
    return b;
}

int lg,ok;
void aduna( int C[],int A[])
{
    int i,t=0;
    lg=max(A[0],C[0]);
    C[0]=lg;
    for(i=1;i<=lg;++i)
    {
        C[i] += (A[i]  + t);
        t=C[i]/10;
        C[i]=C[i]%10;
    }
    if(t > 0)
    {
        ++C[0];
        C[C[0]]=1;
        t=0;
    }
}

int main()
{
    freopen("indep.in","r",stdin);
    freopen("indep.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        M=max(a[i],M);
    }
    cnt[a[1]][0]=1;cnt[a[1]][1]=1;
    vec1[0]=1;vec1[1]=1;
    for(i=2;i<=n;++i)
    {
        for(j=1;j<=M;++j)
            {

                if(mat[j][a[i]] != 0) c=mat[j][a[i]];
                    else
                    {
                        c=cmmdc(j,a[i]);
                        mat[j][a[i]]=c;
                        mat[a[i]][j]=c;
                    }
                if(cnt[j][0]) aduna(cnt[c],cnt[j]);
            }
        aduna(cnt[a[i]],vec1);
    }

    lg=cnt[1][0];
    for(i=lg;i>=1;--i)
        printf("%d",cnt[1][i]);
    if(lg == 0) printf("0\n");
    return 0;
}