#include <fstream>
#define lim 1000000
#define Next ++pos == lim?f.read(buffer, lim), pos = 0:0
#define NMax 510
#define ValMax 1010

using namespace std;

ifstream f ("indep.in");
int pos;
char buffer[lim];
int n, a[NMax], maxim;
int dp[2][ValMax][1024];
int mat[ValMax][ValMax];

inline void Read(int &x)
{
    for (; buffer[pos] < '0' || buffer[pos] > '9'; Next);
    for (x = 0; buffer[pos] >= '0' && buffer[pos] <= '9'; x = x*10 + buffer[pos] - '0', Next);
}

inline void Read()
{
    Read(n);
    int i;
    for (i=1; i<=n; ++i)
        Read(a[i]), maxim = max(maxim, a[i]);
    f.close();
}
inline void Adunare(int *A, int *B)
{
    int i, t = 0;
    for (i=1; i<=A[0] || i<=B[0] || t; ++i, t/=1000000000)
        A[i] = (t += A[i] + B[i]) % 1000000000;
    A[0] = i - 1;
}

inline int cmmdc(int x, int y)
{
    int r;
    while (y)
    {
        r = x%y;
        x = y;
        y = r;
    }
    return x;
}

inline void memset(int *A)
{
    int i;
    for (i=A[0]; i>=0; --i)
        A[i] = 0;
}

inline void Solve()
{
    /// dp[i][j] = numarul de subsiruri existente folosind elemente din primele i cu cmmdc = j
    /// dp[i][j] -> dp[i+1][j]

    int i, p, q, j;
    for (i=1; i<=n; ++i)
        for (j=1; j<=maxim; ++j)
            mat[a[i]][j] = mat[j][a[i]] = cmmdc(a[i], j);
    int unu[2];
    unu[0] = unu[1] = 1;
    for (i=1, p=1, q=0; i<=n; ++i, swap(p, q))
    {
        Adunare(dp[p][a[i]], unu);
        for (j=1; j<=maxim; ++j)
        {
            Adunare(dp[p][j], dp[q][j]);
            Adunare(dp[p][mat[j][a[i]]], dp[q][j]);
        }
        for (j=1; j<=maxim; ++j)
            memset(dp[q][j]);
    }
    freopen ("indep.out", "w", stdout);
    if (dp[q][1][0] == 0)
    {
        printf("0\n");
        fclose(stdout);
        return ;
    }
    printf ("%d", dp[q][1][dp[q][1][0]]);
    for (i=dp[q][1][0] - 1; i; --i)
        printf ("%09d", dp[q][1][i]);
    printf("\n");
    fclose(stdout);
}

int main()
{
    Read();
    Solve();
    return 0;
}