Вам задан массив $$$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]$$$.
