题目描述

我们有一张$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$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。