/*
算法思路：
    对于新开的组，每次遍历数列中剩下的数，如果存在可以放入新组的数，则将该数放入新组，继续从该数的下个数开始向下搜索；
    否则新建一个组，然后重复上述操作。

优化1：如果x可以放到当前组，就没有必要新开一个组
    证明：如果新开一个组可以则到最优解，那么把x这个数放回之前那个组，仍然不影响互质性，所以同样可以得到最优解。
优化2：要按照组合的顺序搜索，在一个组内1、2、3和3、2、1是等价的，所以引入一个start，每次从start开始搜，保证组内的序号是递增的。

*/
#include <iostream>

using namespace std;

const int N = 11;

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;
}

bool check(int g[] , int gc , int i)
{
    for(int j = 0 ; j < gc ; j++)
        if(gcd(p[i] , p[g[j]]) > 1)
            return false;
    return true;
}

void dfs(int g , int gc , int tc , int start)//当前的组数，当前组的数的个数，总共已经放入的数的个数，开始搜的位置
{
    if(g >= ans) return;
    if(tc == n) ans = g;

    bool flag = false;
    for(int i = start ; i < n ; i++)//原数列剩下的数中，是否还存在可以放到当前组中的数
    {
        if(!st[i] && check(group[g] , gc , i))
        {
            st[i] = true;
            group[g][gc] = i;
            dfs(g , gc + 1 , tc + 1 , start + 1);
            st[i] =false;

            flag = true;
        }
    }

    //如果不存在，重新建组
    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;
}