题目描述

将 $n$ 个不同的整数分成若干组，要求每组内的整数互质（任意两个整数的公约数只有 $1$），问至少要分成几组。

输入格式

第 $1$ 行是一个正整数 $n$。

第 $2$ 行是 $n$ 个互不相同的整数。

输出格式

一个整数，最少的组数。

输入输出样例

4
1 2 3 4

2

说明/提示

对于输入样例，满足条件的分组方法有下面 $10$ 种，可知至少要分成 $2$ 组：

1 2 3 | 4 
1 2 | 3 4 
1 2 | 3 | 4 
1 3 4 | 2 
1 3 | 2 | 4 
1 4 | 2 3 
1 | 2 3 | 4 
1 4 | 2 | 3 
1 | 2 | 3 4 
1 | 2 | 3 | 4

👀️ 对于$100\%$ 的数据，$2 \leq n \leq 20$，输入的整数绝对值不超过 $1000$。