#include <bits/stdc++.h>
///Base=100.000.000
///Val=1.000
///N=500
using namespace std;
///
int n, i, j, k, mx, cnt;
int val[501], powers[501][25], ciur[1001];
bitset<1001> check, ok;
long long res;
///
void read();
void solve();
void write();
void formPow(int i);
void diff(int i);
void sum(int i);
void buildCiur();
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("indep.in", "r", stdin);
    scanf("%d", &n);
    for(i=1; i<=n; ++i){
        int x;
        scanf("%d", &x);
        if(!check[x]){
            check[x]=true;
            val[++cnt]=x;
            mx=max(mx, x);
        }
    }
    delete &n;
    fclose(stdin);
}
void solve(){
    powers[0][0]=powers[0][1]=1;
    for(i=1; i<=cnt; ++i) formPow(i);
    for(i=0; i<=cnt; ++i) powers[i][1]=powers[i][1]-i-1;
    buildCiur();
    for(i=2; i<=mx; ++i){
        if(ok[i]) continue;
        int tot=0;
        for(j=i; j<=mx; j+=i) if(check[j]) ++tot;
        if(ciur[i]&1) diff(tot);
        else sum(tot);
    }
}
void write(){
    freopen("indep.out", "w", stdout);
    printf("%d", powers[cnt][powers[cnt][0]]);
    for(i=powers[cnt][0]-1; i>=1; --i){
        for(j=10000000; j>=1; j/=10){
            printf("%d", (powers[cnt][i]/j)%10);
        }
    }
    fclose(stdout);
}
void formPow(int i){
    int j, r=0;
    powers[i][0]=powers[i-1][0];
    for(j=1; j<=powers[i][0]; ++j){
        powers[i][j]=r+2*powers[i-1][j];
        r=powers[i][j]/100000000;
        powers[i][j]%=100000000;
    }
    if(r) powers[i][++powers[i][0]]=r;
}
void diff(int i){
    int j;
    for(j=1; j<=powers[cnt][0]; ++j){
        powers[cnt][j]-=powers[i][j];
        if(powers[cnt][j]<0){
            powers[cnt][j]=100000000-powers[cnt][j];
            --powers[cnt][j+1];
        }
    }
    while(!powers[cnt][powers[cnt][0]]) --powers[cnt][0];
}
void sum(int i){
    int j, r=0;
    for(j=1; j<=powers[cnt][0]; ++j){
        powers[cnt][j]+=r+powers[i][j];
        r=powers[cnt][j]/100000000;
        powers[i][j]%=100000000;
    }
    if(r) powers[cnt][++powers[cnt][0]]=r;
}
void buildCiur(){
    for(i=2; i<=mx; ++i){
        if(ciur[i]) continue;
        for(j=i; j<=mx; j+=i){
            ++ciur[j];
            if(!(j%(i*i))) ok[j]=true;
        }
    }
}