Вам задан массив \(a\), состоящий из \(n\) целых чисел.
Назовем пару индексов \(i\), \(j\) хорошей, если \(1 \le i < j \le n\) и \(\gcd(a_i, 2a_j) > 1\) (где \(\gcd(x, y)\) — наибольший общий делитель чисел \(x\) и \(y\)).
Найдите максимальное количество хороших пар индексов, если вы можете переупорядочить элементы массива \(a\) произвольным образом.
Выходные данные
Для каждого набора выходных данных выведите одно целое число — максимальное количество хороших пар индексов после переупорядочивания элементов массива \(a\).
Примечание
В первом примере из условия элементы массива можно переставить следующим образом: \([6, 3, 5, 3]\).
В третьем примере из условия элементы массива можно переставить следующим образом: \([4, 4, 2, 1, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
3 6 5 3
2
1 7
5
1 4 2 4 1
|
4
0
9
|