友情提示：380元/半年，儿童学编程，就上码丁实验室。
【题目描述】
我们有一张$n$个节点的图，每个节点有一个点权。对于任意两个点，如果它们点权的$gcd$为合数，那么这两个点之间有一条边。
上帝对这张图并不满意，他会删掉图中的一个点来使得剩余图中最大的连通块最小。
你想知道，在上帝操作之后，图中剩余的最大连通块的大小是多少。
【输入】
本题有多组数据。第一行一个整数 $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≤300$，其中8%的数据保证$a_i≤2,000$。
对于40%的数据，保证$n≤5,000$，其中20%的数据保证$a_i≤30,000$。
对于100%的数据，保证$n≤10^5，a_i≤10^7$，其中52%的数据保证$a_i≤10^5$。
对于100%的数据，保证$T≤10，n≥2，a_i≥2$。