#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N=15;
int n;
int a[N];
vector<int>prime[N];//二维数组想取出一维的长度，用vector
int ans=30;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
bool check(int a,int b)
{
    if(gcd(a,b)>1)return false;
    return true;
}
void dfs(int u,int group)//当前的数，当前的组数
{
    if(group>=ans)return;//求最小值可以剪枝
    if(u==n)
    {
        ans=min(ans,group);
        return ;
    }

    for(int i=0;i<group;i++)
    {
        bool flag=true;
        for(int j=0;j<prime[i].size();j++)
        {
            if(!check(a[u],prime[i][j]))
            {
                flag=false;
                break;
            }
        }
        if(flag)//能加就加
        {
            prime[i].push_back(a[u]);
            dfs(u+1,group);
            prime[i].pop_back();
        }
    }
     //另开新组
    prime[group].push_back(a[u]);
    dfs(u+1,group+1);
    prime[group].pop_back();

}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    dfs(0,0);
    cout<<ans<<endl;

    return 0;
}