5510: 连通块（connect）
Memory Limit：512 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
小李有一张n个节点的图，每个节点有一个点权，两个点之间的权值的gcd（最大公约数）不是质数（也不是1），那么两个点之间有一条边。现在删掉图中的一个点（及其和它连接的边）后剩余图的最大连通块的节点数尽可能小。
即将参加2024年CSP-S第二轮的你对这个问题很感兴趣，现在有T组数据你想知道，对于每组数据在进行删除操作后，图中剩余的最大连通块的大小是多少，求这个的最小值。
Input
第一行一个整数T表示数据组数。接下来依次描述各组数据，对于每组数据：每组数据的第一行一个正整数n，表示节点的个数。
第二行n个用空格隔开的正整数，依次描述1号节点到n号节点的点权a_1⋯a_n。
Output
对于每组数据，输出一行一个正整数，表示答案。
Sample Input Copy
3
5
8 4 12 18 9
5
36 20 84 45 231
7
100 200 300 400 500 600 700Sample Output Copy
2
3
6HINT
对于所有的测试数据有：0<n<=10^5,0<a_i<=10^7,1<=T<=10。