import java.lang.*;
import java.io.*;
import java.util.*;



class Main{


    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer stz = new StringTokenizer("");
    static String nextLine() throws Exception {// 读取下一行字符串
        return br.readLine();
    }
    static String next() throws Exception {// 读取下一个字符串
        while (!stz.hasMoreTokens()) {
            stz = new StringTokenizer(br.readLine());
        }
        return stz.nextToken();
    }
    static int nI() throws Exception {// 读取下一个int型数值
        return Integer.parseInt(next());
    }
    static double nD() throws Exception {// 读取下一个double型数值
        return Double.parseDouble(next());
    }
    static long nL() throws Exception {// 读取下一个double型数值
        return Long.parseLong(next());
    }
    static void write(String str) throws Exception{
        bw.write(str);
    }
    static String itoS(int i){
        return Integer.toString(i);
    }
    static void wI(int i) throws Exception{
        write(Integer.toString(i));
    }
    static void wL() throws Exception{
        write("\n");
    }
    static void flush() throws Exception{
        bw.flush();
    }
    public void print() throws  Exception{
        flush();
    }
    public static void main(String[] args) throws Exception{
        Main main = new Main(); main.run(); main.print();
    }


    final int N = 10;
    int n, res = 10;
    // 最多的分组数量
    int[][] g = new int[N][N];
    int[] arr = new int[N];
    // 防止重新走过
    boolean[] st = new boolean[N];
    // 经典gcd
    int gcd(int a, int b){
        return b != 0 ? gcd(b, a % b) : a;
    }
    /**
     *
     * @param cur 需要进行判断的某一个分组
     * @param x  arr[i] 判断 x 是否可以加入这个分组
     * @param len  当前组内的长度
     * @return
     */
    boolean check(int[] cur, int x, int len){
        for (int i = 0; i < len; i++) {
            if (gcd(cur[i], x) > 1) return false;
        }
        return true;
    }

    /**
     *
     * @param u 当前是第几组
     * @param gc 第u组的第几个位置
     * @param start arr组内的第几个位置开始判断 不能加入再说， 能加入的都先加入
     * @param cnt 已经加入的元素数量
     */
    void dfs(int u, int gc, int start, int cnt){
        if (u >= res) return;// 没必要往下了， 当前分组显然不是最优的
        if (cnt == n) res = u;
        boolean flat = true;
        // 设置 start 就是为了能加入的优先加入当前组， 实在碰到不能加入的， 那就得将start = 0 重新爆搜了， st 可以防止已经加入上一组的重新被加入
        for (int i = start; i < n; i++) {
            // 当前arr[i] 这个元素可以加入 g[u] 组里
            if (!st[i] && check(g[u], arr[i], gc)){
                st[i] = true;
                g[u][gc] = arr[i];
                dfs(u, gc + 1, start + 1, cnt + 1);
                st[i] = false;
                flat = false;
            }
        }
        if (flat) dfs(u+1, 0, 0, cnt);
    }


    public void run() throws Exception{
        n = nI();
        for (int i = 0; i < n; i++) {
            arr[i] = nI();
        }
        dfs(1, 0, 0, 0);
        wI(res); wL();
    }
}