B. Переупорядочение массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел.

Назовем пару индексов $$$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$$$.

Пример
Входные данные
3
4
3 6 5 3
2
1 7
5
1 4 2 4 1
Выходные данные
4
0
9
Примечание

В первом примере из условия элементы массива можно переставить следующим образом: $$$[6, 3, 5, 3]$$$.

В третьем примере из условия элементы массива можно переставить следующим образом: $$$[4, 4, 2, 1, 1]$$$.