互质小分队

题目描述

有 $n$ 个小朋友分组，每个小朋友手里都拿一个纸条，每个纸条上都写了一个整数，现在将小朋友们分组，使得每组中任意两个小朋友手上的数字互质。至少要把小朋友分成多少组？

输入格式

第一行是一个正整数 $n$ 。表示小朋友的数量。 第二行是 $n$ 个不大于 $10000$ 的正整数，是小朋友手里的数字。

输出格式

一个正整数，即最少分成多少组。

6
14 20 33 117 143 175

3

提示

#### 数据范围与提示 $1 \le n \le 10$

来源

童程童美