#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

int gcd(int a, int b)
{
    if (!b) return a;
    return gcd(b, a % b);
}

int main() {
    fstream f1, f2;
    int n, i, j, k, p, nr=0, fi, se, m, l;
    deque<int> Q;
    f1.open("indep.in", ios::in);
    f1>>n>>i;
    Q.push_back(i);
    for(i=2; i<=n; i++) {
         f1>>k;
         p=Q.size();
         for(j=0; j<p; j++) {
              fi=Q[j];
              m=gcd(fi, k);
              Q.push_back(m);
         }
         Q.push_back(k);
    }
    f1.close();

    p=Q.size();
    for(j=0; j<p; j++) {
         fi=Q[j];
         if(fi==1) {
              nr++;
         }
    }

    f2.open("indep.out", ios::out);
    f2<<nr<<endl;
    f2.close();
    return 0;
}