#include <fstream>
#include <cstring>

#define BASE 1000000000

using namespace std;

ifstream f("indep.in");
ofstream g("indep.out");

unsigned long long n , v[505] , dp1[1005] , dp2[1005] , aux[305] , NMAX;

void adun(int a[] , int b[]);
void afis(int a[]);
int gcd(int a , int b) {
    int r = a % b;
    while(r) {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

int main() {
    aux[0] = 1;
    aux[1] = 1;

    f >> n;

    for(int i = 1 ; i <= n ; ++i) {
        f >> v[i];
        NMAX = max(NMAX , v[i]);
    }

    for(int i = 1 ; i <= n ; ++i) {
        if(i % 2 == 1) {
            memset(dp1 , 0 , sizeof(dp1));
        }
        else {
            memset(dp2 , 0 , sizeof(dp2));
        }
        for(int j = 1 ; j <= NMAX ; ++j) {
            if(i % 2 == 0) {
                dp2[gcd(j , v[i])] += dp1[j];
                dp2[j] += dp1[j];
            }
            else {
                dp1[gcd(j , v[i])] += dp2[j];
                dp1[j] += dp2[j];
            }
        }

        if(i % 2 == 1) {
            ++dp1[v[i]];
        }
        else {
            ++dp2[v[i]];
        }
    }

    if(n % 2 == 1)
        g << dp1[1];//afis(dp1[1]);
    else
        g << dp2[1];//afis(dp2[1]);
    return 0;
}

void adun(int a[] , int b[]) {
    int t = 0;
    a[0] = max(b[0] , a[0]);
    for(int i = 1 ; i <= a[0] ; ++i) {
        a[i] = b[i] + a[i] + t;
        t = a[i] / BASE;
        a[i] = a[i] % BASE;
    }

    while(t) {
        a[++a[0]] = t % BASE;
        t /= BASE;
    }
}

void afis(int a[]) {
    for(int i = a[0] ; i >= 1 ; --i) {
        g << a[i];
    }
}