CF1535B Array Reodering

给定一个包含 $n$ 个整数的数组 $a$。 我们称一对下标 $i$、$j$ 是“好”的，如果 $1 \le i < j \le n$ 且 $\gcd(a_i, 2a_j) > 1$（其中 $\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数）。 如果你可以任意重排数组 $a$，请你求出最多有多少对“好”的下标对。

第一行包含一个整数 $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$。

对于每个测试用例，输出一个整数，表示在可以任意重排数组 $a$ 的情况下，最多有多少对“好”的下标对。

在第一个样例中，数组元素可以重排为 $[6, 3, 5, 3]$。 在第三个样例中，数组元素可以重排为 $[4, 4, 2, 1, 1]$。 由 ChatGPT 4.1 翻译