CF1535B.Array Reodering

You are given an array $a$ consisting of $n$ integers.

Let's call a pair of indices $i$, $j$ good if $1 \le i \lt j \le n$ and $\gcd(a_i, 2a_j) \gt 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.

给你一个包含 $n$ 个整数的数组 $a$。

我们称一对下标 $i, j$ 是“好的”，当且仅当 $1 \le i \lt j \le n$ 且 $\gcd(a_i, 2a_j) \gt 1$（其中 $\gcd(x, y)$ 表示 $x$ 与 $y$ 的最大公约数）。

如果你可以以任意方式重排数组 $a$，求最多能有多少对“好的”下标对。

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$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2000$）—— 数组中元素的个数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^5$）。

保证所有测试用例的 $n$ 之和不超过 $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.

对于每个测试用例，输出一个整数——即在你可以以任意方式重排数组 $a$ 的前提下，所能得到的“好”索引对的最大数量。

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]$.

在第一个例子中，数组元素可以重新排列为：$[6, 3, 5, 3]$。

在第三个例子中，数组元素可以重新排列为：$[4, 4, 2, 1, 1]$。