You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

游戏角色组队

题目描述

在一个冒险游戏中，有 $n$ 名角色，每个角色都有一个独特的战斗属性值。为了完成任务，这些角色需要分成若干个小队，每个小队中的任何两个角色的战斗属性值必须互质（即两个数的最大公约数为 $1$）。现在需要知道，至少要将这些角色分成多少个小队？

输入

第一行是一个正整数 $n$，表示角色的数量，$1 \leq n \leq 10$。

第二行是 $n$ 个正整数，表示每个角色的战斗属性值。每个属性值不大于 $10000$。

输出

输出一个正整数，即最少需要的小队数量。

样例

输入样例 1

6
14 20 33 117 143 175

输出样例 1

3

样例解释

将角色分组的最优方式如下：

• 第 1 组：14, 33, 143（它们两两互质）
• 第 2 组：20, 175（它们两两互质）
• 第 3 组：117（单独一组）

因此，最少需要 3 个小队。

数据范围

• $1 \leq n \leq 10$
• 每个角色的属性值为不大于 $10000$ 的正整数。