#include <cstdio>
#include <algorithm>
using namespace std;

int n, NR;
int p[180], w[1005], nr[1005], a[1005], Sol[1005];
bool f[1005];
inline void back(int k, int nr, int P){
    if(P > 1000) return ;
    if(k > 0) w[P] = nr + 1;
    for(int i = k + 1; i <= NR ; ++i)
        back(i, 1 - nr, P * p[i]);
}
const int MOD = 1000;
inline void add(int A[], int B[]){
    A[0] = max(A[0], B[0]);
    int t = 0;
    for(int i = 1; i <= A[0] ; ++i){
        A[i] = A[i] + B[i] + t;
        t = A[i] / MOD; A[i] %= MOD;
    }
    if(t > 0) A[++A[0]] = t;
}inline void scad(int A[], int B[]){
    int t = 0;
    for(int i = 1; i <= B[0] ; ++i){
        A[i] = A[i] - B[i] + t;
        if(A[i] < 0) A[i] += MOD, t = -1;
        else t = 0;
    }
    while(t){
        A[A[0]] += t;
        if(A[A[0]] < 0) A[A[0]] += MOD, t = -1;
        else t = 0;
    }
    while(A[A[0]] == 0) --A[0];
}
inline void inm(int A[], int B[]){
    A[0] = max(A[0], B[0]);
    int t = 0;
    for(int i = 1; i <= A[0] ; ++i){
        A[i] = A[i] * B[i] + t;
        t = A[i] / MOD; A[i] %= MOD;
    }
    while(t > 0){
        A[++A[0]] = t % MOD;
        t = t / MOD;
    }
}
int A[1005], P[1005];
inline int *put(int n){
    A[0] = P[0] = A[1] = 1; P[1] = 2;
    for(int i = 0; (1 << i) <= n ; ++i){
        if((n & (1 << i))) inm(A, P);
        inm(P, P);
    }
    A[A[0]]--;
    return A;
}
int main()
{
    freopen("indep.in", "r", stdin);
    freopen("indep.out", "w", stdout);
    for(int i = 2; i <= 1000 ; ++i){
        if(!f[i]){
            p[++NR] = i;
            for(int j = i * 2; j <= 1000 ; j += i)
                f[j] = 1;
        }
    }
    back(0, 0, 1);
    scanf("%d", &n);
    for(int i = 1; i <= n ; ++i)
        scanf("%d", &a[i]);
    nr[1] = n;
    w[1] = 2;
    for(int i = 2; i <= 1000 ; ++i)
        for(int j = 1; j <= n ; ++j)
            if(a[j] % i == 0) ++nr[i];
    add(Sol, put(n));
    for(int i = 2; i <= 1000 ; ++i){
        if(!nr[i]) continue ;
        if(w[i] == 2) scad(Sol, put(nr[i]));
        else if(w[i] == 1)add(Sol, put(nr[i]));
    }
    if(Sol[0] == 0) printf("0");
    printf("%d", Sol[Sol[0]]);
    for(int i = Sol[0] - 1; i >= 1 ; --i){
        int aux = Sol[i];
        while(aux < MOD / 10) printf("0"), aux *= 10;
        printf("%d", Sol[i]);
    }
    return 0;
}