#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<pair<int, int> > Q;
    f1.open("indep.in", ios::in);
    f1>>n>>i;
    Q.push_back(make_pair(i, 1));
    for(i=2; i<=n; i++) {
         f1>>k;
         p=Q.size();
         for(j=0; j<p; j++) {
              fi=Q[j].first; se=Q[j].second;
              m=gcd(fi, k);
              Q.push_back(make_pair(m, se+1));
         }
         Q.push_back(make_pair(k, 1));
    }
    f1.close();

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

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