连通块（connect）

【问题描述】

​ 小 $\text{X}$ 有一张 $n$ 个节点的图，每个节点有一个点权。但让 小 $\text{X}$ 感到生气的是，这张图上并没有任何的边，于是他决定钦点一些边。

​ 小 $\text{X}$ 喜欢 $gcd$ 和合数，所以 小 $\text{X}$ 的钦点规则与 $gcd$（最大公约数）和合数有关。具体来说，对于 $2$ 个点，如果它们点权的 $gcd$ 为合数，那么 小 $\text{X}$ 就会钦点它们之间连一条边。

​ 小 $\text{Y}$ 看到了 小 $\text{X}$ 稚的行为，决定把他批判一番。他知道 小 $\text{X}$ 热衷于连通块，因此他会删掉图中的一个点来使得剩余图中最大的连通块最小。

​ 即将参加 $\text{NOIP2023}$ 的你对这个问题很感兴趣，于是你想知道，在 小 $\text{Y}$ 操作之后，图中剩余的最大连通块的大小是多少。

【输入格式】

​ 本题有多组数据。

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

​ 第一行 $1$ 个正整数 $n$，表示节点的个数。

​ 第二行 $n$ 个用空格隔开的正整数，依次描述了 $1$ 号节点到 $n$ 号节点的点权 $a_1 . . . a_n$。

【输出格式】

​ 对于每组数据，输出一行一个整数，表示答案。

【样例输入1】

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

【样例输出1】

2
3
6

【样例2】

​ 见下发文件中。

【数据范围及约定】

​ 对于 $16\%$ 的数据，保证 $n \le 300$，其中 $8\%$ 的数据保证 $a_i \le 2, 000$；

​ 对于 $40\%$ 的数据，保证 $n \le 5, 000$，其中 $20\%$ 的数据保证 $a_i \le 30, 000$；

​ 对于 $100\%$ 的数据，保证 $n \le 10^5，a_i \le 10^7$，其中 $52\%$ 的数据保证 $a_i \le 10^5$；

​ 对于 $100\%$ 的数据，保证 $T \le 10，n \ge 2，a_i \ge 2$。