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

using namespace std;

const int N=10;
int n;
int p[N];
int group[N][N];
bool st[N];
int ans=N;

int gcd(int a,int b)
{
    return b? gcd(b,a%b): a;
}
//互质：两个数只要1这个公共的因子
bool check(int group[],int gc,int i)
{
    for(int j=0;j<gc;j++)
      if(gcd(p[group[j]],p[i])>1)
      return false;
    return true;
}
//当前的组数，当前组的数的个数，总共已经放入的数的个数，开始搜的位置
void dfs(int g,int gc,int tc,int start)
{
    if(g>=ans)  return ;//如果当前的组数大于ans，直接下一个一条路径
    if(tc==n)  ans=g;   //如果放入组内的数的个数等于n，那么将组数赋给ans

    bool flag=true;//判断这个组内是否可以添加元素
    //原数列剩下的数中，是否还存在可以放到当前组中的数
    for(int i=start;i<n;i++) 
      if(!st[i]&&check(group[g],gc,i))
      //这个数没有被标记，并且这个数和gc这个组内的所有数全部互质
      {
          st[i]=true;   //将这个数进行标记
         group[g][gc]=i;   //将这个数i赋值为第g组的第几个数
          dfs(g,gc+1,tc+1,i+1);
          st[i]=false;   //恢复现场

          flag=false;
      }
    //不存在，再开一个组
    if(flag)  dfs(g+1,0,tc,0);
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>p[i];
    dfs(1,0,0,0);
    //当前的组数，当前组的数的个数，总共已经放入的数的个数，开始搜的位置
    cout<<ans<<endl;
    return 0;
}