#include <cstdio>

int v[501],nr,x;
bool b[501][501];

void numarare (int f)
{
    bool tr=0;
    for(int i=1; i<=v[0] && tr==0; i++)
    {
        for(int j=i+1; j<=v[0]; j++)
        {
            if(b[i][j]==1 && v[i] && v[j])
            {
                tr=1;
                break;
            }
        }
    }
    if(tr==1)
    {
        nr++;
        for(int k=f+1; k<=v[0]; k++)
        {
            if(v[k]>0)
            {
                x=v[k];
                v[k]=0;
                numarare(k);
                v[k]=x;
            }
        }
    }
}

bool cmmdc(int a, int b)
{
    int c;
    while(b)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a==1;
}

int main()
{
    freopen("indep.in","r",stdin);
    freopen("indep.out","w",stdout);

    int n;
    scanf("%d",&n);
    v[0]=n;
    for(int i=1; i<=n ;i++)
        scanf("%d",&v[i]);

    for(int i=1; i<=n ;i++)
        for(int j=i+1; j<=n; j++)
            if(cmmdc(v[i],v[j]))
            {
                b[i][j]=1;
                b[j][i]=1;
            }


    numarare(0);

    printf("%d",nr);
    return 0;
}