小 \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，