题目描述

给定一个包含 $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 翻译

样例

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

4
0
9