9462 - 连通块(connect)
时间限制 : 1 秒
内存限制 : 512 MB
小李有一张 n个节点的图，每个节点有一个点权，两个点之间的权值的gcd(最大公约数)不是质数(也不是1)，那么两个点之间有一条边。现在删掉图中的一个点(及其和它连接的边）后剩余图的最大连通块的节点数尽可能小。
即将参加 2024年CSP-S第二轮的你对这个问题很感兴趣，现在有T组数据你想知道，对于每组数据在进行删除操作后，图中剩余的最大连通块的大小是多少，求这个的最小值。
输入
第一行一个整数T表示数据组数。接下来依次描述各组数据，对于每组数据：
每组数据的第一行一行一个正整数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
提示
【样例解释1】
第一组测试例：当删除节点权值为12的点后，图分为{4,8} {18,9}两个连通块，两个连通块的节点数都为2。
第二、三组同理⋯⋯
【数据范围】
对于所有的测试数据有： 0< n ≤ 10^5, 0 < a_i ≤ 10^7,1 ≤ T ≤ 10。
来源
云南编程挑战赛