Array Reodering

题意翻译

$t$ 组询问，每次给定一个长度为 $n$ 的序列 $a$。定义数对 $(i,j)$ 是优美的当且仅当 $1\leq i<j\leq n,\gcd(a_i,2\times a_j)>1$。请求出将原序列重排后可以产生的优美数对个数的最大值。 $t\leq 1000,2\leq n\leq 2000,\sum n\leq 2000,1\leq a_i\leq 10^5$。 translated by LinkZelda

题目描述

You are given an array $ a $ consisting of $ n $ integers. Let's call a pair of indices $ i $ , $ j $ good if $ 1 \le i < j \le n $ and $ \gcd(a_i, 2a_j) > 1 $ (where $ \gcd(x, y) $ is the greatest common divisor of $ x $ and $ y $ ). Find the maximum number of good index pairs if you can reorder the array $ a $ in an arbitrary way.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The first line of the test case contains a single integer $ n $ ( $ 2 \le n \le 2000 $ ) — the number of elements in the array. The second line of the test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^5 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2000 $ .

输出格式

For each test case, output a single integer — the maximum number of good index pairs if you can reorder the array $ a $ in an arbitrary way.

输入输出样例

输入样例 #1

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

输出样例 #1

4
0
9

说明

In the first example, the array elements can be rearranged as follows: $ [6, 3, 5, 3] $ . In the third example, the array elements can be rearranged as follows: $ [4, 4, 2, 1, 1] $ .