A. Средняя высота
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Sayaka Saeki является членом студенческого совета, в который входит $$$n$$$ других членов (не считая Sayaka). $$$i$$$-й член совета имеет высоту $$$a_i$$$ миллиметров.

Наступает конец учебного года, и Sayaka хочет сфотографировать всех остальных членов студенческого совета. Будучи трудолюбивой девушкой и перфекционисткой, она хочет выстроить всех членов в ряд таким образом, чтобы количество последовательных пар фотогеничных членов было как можно больше.

Пара из двух последовательных членов совета $$$u$$$ и $$$v$$$ в строке считается фотогеничной, если их средний рост — целое число, т.е. $$$\frac{a_u + a_v}{2}$$$ — целое число.

Помогите Sayaka расположить остальных членов в ряд таким образом, чтобы максимизировать количество фотогеничных последовательных пар.

Входные данные

В первой строке содержится одно целое число $$$t$$$ ($$$1\le t\le 500$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое $$$n$$$ ($$$2 \le n \le 2000$$$)  — число других членов совета.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$)  — высоты каждого из остальных членов совета в миллиметрах.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2000$$$.

Выходные данные

Для каждого набора входных данных выведите в одной строке $$$n$$$ целых чисел — высоты других членов в порядке, который дает наибольшее количество фотогеничных последовательных пар. Если таких порядков несколько, выведите любой из них.

Пример
Входные данные
4
3
1 1 2
3
1 1 1
8
10 9 13 15 3 16 9 13
2
18 9
Выходные данные
1 1 2 
1 1 1 
13 9 13 15 3 9 16 10 
9 18
Примечание

В первом наборе входных данных есть одна фотогеничная пара: $$$(1, 1)$$$ — фотогенична, так как $$$\frac{1+1}{2}=1$$$ — целое число, а $$$(1, 2)$$$ — нет, так как $$$\frac{1+2}{2}=1.5$$$ — нецелое число.

Во втором наборе входных данных обе пары фотогеничны.