#include <cstdio>
#include <iostream>
#define VAL_MAX 1000

using namespace std;
int v[501],p2[501][1000],ss[501][1000],ciur[VAL_MAX+1],f[1001],s[1000];
void adunss (int i){
    int j,t=0;
    for (j=1;j<=max(p2[i-1][0],ss[i-1][0]);j++){
        ss[i][j]=p2[i-1][j]+ss[i-1][j]+t;
        t=ss[i][j]/10;
        ss[i][j]%=10;
    }
    ss[i][0]=max(p2[i-1][0],ss[i-1][0]);
    if (t)
        ss[i][++ss[i][0]]=1;
}
void inmult2 (int i){
    int j,t=0;
    for (j=1;j<=p2[i-1][0];j++){
        p2[i][j]=p2[i-1][j]*2+t;
        t=p2[i][j]/10;
        p2[i][j]%=10;
    }
    p2[i][0]=p2[i-1][0];
    while (t){
        p2[i][++p2[i][0]]=t%10;
        t/=10;
    }
}
void adun (int n,int m){
    int i,t=0;
    // la ss[n] il adun pe p
    for (i=1;i<=ss[n][0];i++){
        ss[n][i]=ss[n][i]+ss[m][i]+t;
        t=ss[n][i]/10;
        ss[n][i]%=10;
    }
    if (t!=0)
        ss[n][++ss[n][0]]=1;
}
void scad (int n,int m){
    // la ss[n] il scad pe p
    int i,t=0;
    for (i=1;i<=ss[n][0];i++){
        ss[n][i]=ss[n][i]-ss[m][i]-t;
        if (ss[n][i]<0)
            t=1;
        else t=0;
        if (t)
            ss[n][i]+=10;
    }
    while (ss[n][0]>1 && !ss[n][ss[n][0]])
        ss[n][0]--;
}
int main()
{
    FILE *fin=fopen ("indep.in","r");
    FILE *fout=fopen ("indep.out","w");
    int n,i,prod,nrf,j,d,elem,cop,div,me,nr,e;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d",&v[i]);
    p2[1][0]=ss[1][1]=ss[1][0]=1;
    p2[1][1]=2;
    for (i=2;i<=n;i++){
        adunss (i);
        inmult2 (i);
    }
    // ss reprezinta nr de subsiruri care se pot forma cu n numere
    // p2[n] este 2^n
    ciur[1]=1;
    for (i=2;i<=VAL_MAX;i++){
        if (ciur[i]==0)
            for (j=2*i;j<=VAL_MAX;j+=i)
                ciur[j]++;
    }
    // ciur[j] reprezinta nr de divizori primi ai lui j
    // cand j e prim, ciur[j]=0
    for (i=1;i<=1000;i++){
        me=0;
        d=2;
        nr=i;
        while (d*d<=nr){
            e=0;
            while (nr%d==0){
                e++;
                nr/=d;
            }
            d++;
            me=max(me,e);
        }
        if (me>1)
            s[i]=1;
    }
    s[1]=1;
    for (i=1;i<=n;i++){
        d=1;
        while (d*d<=v[i]){
            if (v[i]%d==0){
                if (s[v[i]/d]==0)
                    f[v[i]/d]++;
                if (d*d<v[i]){
                    if (s[d]==0)
                        f[d]++;
                }
            }
            d++;
        }
    }
    // f[i] e diferit de 0 doar daca EXISTA v[j] a.i. v[j]%i==0
    elem=0;
    for (i=1;i<=1000;i++){
        if (f[i]!=0){
            printf ("%d %d\n",i,ciur[i]);
            if (ciur[i]%2==0 && ciur[i]!=0)
               adun (n,f[i]);
            else scad (n,f[i]);
        }
    }
    // avem in prim TOTI factorii primi ai numerelor
    /*while (!gen[0]){
        j=elem;
        while (gen[j]){
            gen[j]=0;
            j--;
        }
        if (!j)
            break;
        gen[j]=1;
        nrf=0;
        prod=1;
        for (j=1;j<=elem;j++){
            if (gen[j]){
                prod*=prim[j];
                nrf++;
            }
        }
        if (prod<=1000 && ciur[prod]%2==0 && ciur[prod]!=0)
            // produsul se va aduna
            adun (n,f[prod]);
        else if (prod<=1000)
            scad (n,f[prod]);
        // produsul se va scadea
    }*/

    if (ss[n][0]==0)
        ss[n][0]=1;
    for (i=ss[n][0];i>0;i--)
        fprintf (fout,"%d",ss[n][i]);
    return 0;
}