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

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

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

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

本题有多组数据。

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

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

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

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

【数据范围及约定】

对于 $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，