给定包含 n  个元素的序列 a[1],a[2],...,a[n] 。
对于一对索引 i,j ，若 1≤i<j≤n 且 gcd(a[i],2*a[j])>1 ，则称其为优美的索引对。
现在你可以对数组进行重新排列，求最大的优美的索引对数量。

第一行输入一个整数 T (1≤T≤10^3) ，表示数据组数。
接下来 2T 行，每两行表示一组数据
每组数据第一行包含一个整数 n (2≤n≤2·10^3) ，表示序列长度。
每组数据第二行包含 n 个整数 a[1],a[2],...,a[n] (1≤a[i]≤10^5) ，表示序列。

保证所有 n 之和不超过 2·10^3 。

对于每组数据输出一行包含一个整数，表示最大的优美的索引对数量。

3
4
3 6 5 3
2
1 7
5
1 4 2 4 1

4
0
9