#include <bits/stdc++.h>
using namespace std;

int generateSubsequences(vector<int> &arr)
{
    int n = arr.size();
    int totalSubsequences = (1 << n);
    int ans = 0;

    for (int i = 0; i < totalSubsequences; ++i)
    {
        vector<int> subsequence;

        for (int j = 0; j < n; ++j)
        {
            if (i & (1 << j))
            {
                subsequence.push_back(arr[j]);
            }
        }

        if (subsequence.size() >= 1)
        {
            int result = subsequence[0];
            for (int k = 1; k < subsequence.size(); ++k)
                result = __gcd(result, subsequence[k]);

            if (result == 1)
                ans++;
        }
    }

    return ans;
}

int main()
{
    //ifstream cin("indep.in");
    //ofstream cout("indep.out");
    int n;
    cin >> n;
    vector<int> arr(n);

    for (int i = 0; i < n; ++i)
        cin >> arr[i];

    cout << generateSubsequences(arr);
    return 0;
}