题目描述

​小 $\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$。

输出格式

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

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

2
3
6

数据规模与约定

​对于 $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$。

大样例

大样例下载