#include <iostream>
#include <fstream>

using namespace std;


#define nmax 501
#define Valmax 1002
#define Cifmax 1000
#define base 1000000000

int n, a[nmax], dp[2][Valmax][Cifmax];
int Max = 0; // valoarea maxima din sir

void citeste(){

    scanf("%d\n", &n);

    for(int i=1; i<=n; i++) scanf("%d\n", &a[i]), Max = max(Max, a[i]);

}

int cmmdc(int a, int b){

    if (b == 0) return a;
    return cmmdc(b, a%b);

}
/*
void aduna(int a[], int b[]){

    //!!! daca schimb in b ramane si in afara procedurii
    //=> c[] = b[] si schimb doar c-ul
    //a = a + b;
    int c[Cifmax];
    for(int i=0; i<Cifmax; i++) c[i] = 0;
    for(int i=0; i<=b[0]; i++) c[i] = b[i];

    //cazul cand b[0] > a[0]
    if (c[0] > a[0]){
        for(int i=a[0]+1; i<=c[0]; i++) a[i] = 0;//pun zerouri
        a[0] = c[0];//ii zic ca acum are b[0] cifre
    } // e de ajuns atat; cazul cand a[0] >= b[0] nu ma intereseaza ca in b[0] am oricum 0

    int rest = 0;
    for(int i=1; i<=a[0]; i++){
        a[i] += c[i] + rest;
        rest = a[i] / 1000000000;//tin zecile
        a[i] = a[i] % 1000000000;//tin ultima cifra
    }

    if (rest) a[ ++a[0] ]  = rest;

}
*/

void aduna(int a[], int b[])
{
    int i, t = 0;

    for (i = 1; i <= a[0] || i <= b[0] || t; ++i, t /= base)
        a[i] = (t += a[i] + b[i]) % base;
    a[0] = i - 1;
}

void sterge(int a[][Cifmax]){

    for(int i=1; i<=Max; i++){
        for(int j=1; j<=a[i][0]; j++){
            a[i][j] = 0;
        }
        a[i][0] = 0;
    }

}

void rezolva(){

    //nr de subsiruri pentru care cel mai mare numar care le dividie pe toate nr din subsir sa fie 1
    //dp[i][j] = numarul de subsirui din primele i avand cmmdc-ul j
    //fac metoda si inapoi si inainte :)) folosindu-ma de i-1,j;
    //trebuie numere mari :-"
    //cel mai rau caz cred ca e de genul : suma Comb de n elemente luate cate k, k = 1,n;

    int linie = 1;
    for(int i=1; i<=n; i++){
        dp[linie][ a[i] ][0] = 1;//initalizez dinamica  : cazul cand il iau doar pe a[i];
        dp[linie][ a[i] ][1] = 1;
        for(int j=1; j<=Max; j++){//ma aflu in (i,j) continui i,j din i-1,j nu adaug a[i] si 2 : continui i,cmmdc(j,a[i]) cu i,j
            //dp[i][j] += dp[i-1][j];//nu ma folosesc a[i];
            //dp[i][ cmmdc(j,a[i]) ] += dp[i-1][j];//si acum ma folosesc de a[i];
            aduna(dp[linie][j], dp[1-linie][j]);
            aduna(dp[linie][ cmmdc(j,a[i]) ], dp[1-linie][j]);
        }
        sterge(dp[1-linie]);
        linie = 1-linie;
    }

    //g << dp[n][1] << "\n";
    //am numarul de forma unitati zeci, sute etc =>
    printf("%d", dp[1-linie][1][ dp[1-linie][1][0] ] );
    for(int i=dp[1-linie][1][0]-1; i>=1; i--){
        printf("%.9d", dp[1-linie][1][i]);
    }

}

int main(){

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

    citeste();
    rezolva();


    return 0;

}