题目描述

广场上有 $n$ 个人，编号为 $1 \sim n$，第 $i$ 个人的权值为 $a_i$。 他们之间存在特殊的朋友圈关系：

• 对于两个 $x, y$，若 $\gcd(a_x, a_y)$ 为合数，则 $x, y$ 为直接朋友。
• 对于三个 $x, y, z$，若 $x, y$ 为朋友，$y, z$ 为朋友，则 $x, z$ 为间接朋友。

ws.hcl 需要选出一个人的集合作为朋友圈，满足集合内任意两个个体均为直接或间接的朋友。

在此之前，ws.hcl 必须强制删去一个人，注意移去一个人之后可能会破坏某些间接朋友的关系。

求对于所有 $n$ 种移去人的方案，ws.hcl 能选出的最大集合大小的最小值。

输入格式

从文件 friend.in 中读入数据。

• 第一行一个整数 $T$ 表示数据组数。接下来依次描述各组数据。 对于每组数据：

  • 第一行一个整数 $n$，表示总人数。
  • 第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每个人的权值。

输出格式

输出到文件 friend.out 中。

对于每组数据，输出一行一个整数，表示最大集合大小。

样例 #1

样例输入 #1

3
5
8 4 12 18 9
6
36 20 84 45 231 7
7
100 200 300 400 500 600 700

样例输出 #1

2
3
6

样例 #2

见附加文件中的 friend2.in 和 friend2.ans。

数据范围

对于所有数据：

• $1 \le T \le 10$；
• $2 \le n \le 10^5$；
• $2 \le a_i \le 10^7$。

每个测试点的具体限制如下表所示：