Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

The ugliness of a string is defined as the count of two consecutive ones i.e. "11" in the given string. For example, the ugliness of string "10111" is $2$.  

You are given an array $A$ of $N$ integers and you have to find any ordering of the array such that the ugliness of the concatenated string of the binary representations of the integers (without leading zeros) is minimum.

------  Input ------

The first line of the input contains an integer $T$ denoting the number of test cases. Then $T$ test cases follow.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1},A_{2},\ldots,A_{N}$.

------  Output ------
For each test case, output an ordering of $A$ such that the ugliness of the array is minimum. If there are multiple answers, you may output any.

------  Constraints ------
$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 1000$
$1 ≤ A_{i} ≤ 10^{9}$ 

------  Subtasks ------
Subtask #1 (100 points): Original constraints.

----- Sample Input 1 ------ 
2 
3
3 6 5
2
7 6
----- Sample Output 1 ------ 
5 6 3
6 7
----- explanation 1 ------ 
Test Case 1: The binary representations of $[5, 6, 3]$ are $[101, 110, 11]$ and the concatenated string would be "10111011" which has ugliness $3$. This is the minimum possible. $[6, 5, 3]$ is also valid. 

Test Case 2: The binary representations of $[6, 7]$ are $[110, 111]$ and the concatenated string would be "110111" which has ugliness of $3$. This is the minimum possible. $[7, 6]$ is not valid as it has ugliness of $4$.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	nli = list(map(int, input().split()))
	odli = list()
	evli = list()
	for a in nli:
		if a & 1:
			odli.append(a)
		else:
			evli.append(a)
	lst = evli + odli
	print(*lst)


for z in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = []
	for x in a:
		if x % 2 == 0:
			b.append(str(x))
	for x in a:
		if x % 2 != 0:
			b.append(str(x))
	print(' '.join(b))


t = int(input())
for tests in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	res = []
	for i in range(len(a)):
		if a[i] % 2 == 0:
			res.append(a[i])
	for i in range(len(a)):
		if a[i] % 2 != 0:
			res.append(a[i])
	for i in range(len(res)):
		print(res[i], end=' ')
	print()


mod = 1000000007

def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())

def main():
	evens = []
	odds = []
	for ele in lst:
		if ele % 2 == 0:
			evens.append(ele)
		else:
			odds.append(ele)
	ans = []
	ans.extend(evens + odds)
	print(*ans)
t = int(input())
for _ in range(t):
	n = int(input())
	lst = integer_list()
	main()


def listin():
	a = list(map(int, input().split()))
	return a
for tastcas in range(int(input())):
	n = int(input())
	a = listin()
	b = []
	for i in a:
		if bin(i)[2:][-1] == '0':
			b = [i] + b
		else:
			b = b + [i]
	for i in b:
		print(i, end=' ')
	print()


test = int(input())
for i in range(test):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	even = []
	odd = []
	ans = []
	for j in range(n):
		if l[j] % 2 == 0:
			even.append(l[j])
		else:
			odd.append(l[j])
	ans = even + odd
	for p in ans:
		print(str(p), end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ev = []
	od = []
	for i in l:
		if i & 1:
			od.append(i)
		else:
			ev.append(i)
	ans = ev + od
	print(*ans)


try:
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		evens = []
		odds = []
		for i in arr:
			if i % 2 == 0:
				evens.append(str(i))
			else:
				odds.append(str(i))
		ans = evens + odds
		print(' '.join(ans))
except:
	pass


import sys
import copy
import math
import heapq
import threading
from queue import Queue
isIo = False
threading.stack_size(67108864)
sys.setrecursionlimit(10 ** 6)
if isIo:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
isTakeTestCase = True

def scanIntList():
	return map(int, input().split())

def printList(lst):
	for elem in lst:
		print(elem, end=' ')
	print()

def solve():
	n = int(input())
	lst = scanIntList()
	even = []
	odd = []
	for num in lst:
		if num % 2 == 1:
			odd.append(num)
		else:
			even.append(num)
	for num in even:
		print(num, end=' ')
	for num in odd:
		print(num, end=' ')
	print()
	pass

def driver():
	testCases = 1
	if isTakeTestCase:
		testCases = int(input())
	for i in range(testCases):
		solve()
driver()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	lo = []
	le = []
	for i in range(0, n):
		if l[i] % 2 == 0:
			le.append(l[i])
		else:
			lo.append(l[i])
	for i in range(0, len(le)):
		print(le[i], end=' ')
	for i in range(0, len(lo)):
		print(lo[i], end=' ')
	print()


for t in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	(odd, even, ans) = ([], [], [])
	string = ''
	for num in lst:
		if num % 2 == 0:
			even.append(num)
		else:
			odd.append(num)
	for num in even:
		string += str(bin(num)[2:])
		ans.append(num)
	for num in odd:
		string += str(bin(num)[2:])
		ans.append(num)
	for num in ans:
		print(num, end=' ')
	print('')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	a = []
	b = []
	ans = []
	for j in range(n):
		if l[j] % 2 == 0:
			a.append(l[j])
		else:
			b.append(l[j])
	ans = a + b
	for k in ans:
		print(str(k), end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	for x in range(n - 1, -1, -1):
		if l[x] % 2 != 0:
			tmp = l[-1]
			l[-1] = l[x]
			l[x] = tmp
			break
	print(' '.join((str(s) for s in l)))


try:
	for t in range(int(input())):
		N = int(input())
		A = list(map(int, input().split()))
		odd = []
		even = []
		for num in A:
			if num % 2 == 0:
				even.append(num)
			else:
				odd.append(num)
		result = []
		string = ''
		for num in even:
			string += str(bin(num)[2:])
			result.append(num)
		for num in odd:
			string += str(bin(num)[2:])
			result.append(num)
		for num in result:
			print(num, end=' ')
		print('')
except:
	pass


t = int(input())
for i in range(0, t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	even = []
	odd = []
	for j in arr:
		if j % 2 == 0:
			even.append(j)
		else:
			odd.append(j)
	print(*even, sep=' ', end=' ')
	print(*odd, sep=' ')


for _ in range(int(input())):
	n = int(input())
	li = [int(i) for i in input().split()]
	even = []
	odd = []
	for i in li:
		if i % 2 == 0:
			even.append(str(i))
		else:
			odd.append(str(i))
	s = ' '.join(even) + ' ' + ' '.join(odd)
	print(s)


testcases = int(input())
for testcase in range(testcases):
	length = int(input())
	nums = list(map(int, input().split()))[:length]
	odd = []
	even = []
	for num in nums:
		if num % 2 == 0:
			even.append(num)
		else:
			odd.append(num)
	for item in even + odd:
		print(item, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	even = []
	odd = []
	for i in arr:
		if i & 1:
			odd.append(i)
		else:
			even.append(i)
	for i in even:
		print(i, end=' ')
	for j in odd:
		print(j, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 1):
		if a[i] % 2 != 0:
			(a[i], a[n - 1]) = (a[n - 1], a[i])
	print(*a)


from collections import *
for u in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(l, d) = ([], [])
	a.sort()
	for i in range(n):
		if a[i] % 2 == 1:
			l.append(a[i])
		else:
			d.append(a[i])
	ka = d + l
	print(*ka)


t = int(input())
while t != 0:
	n = int(input())
	arr = [int(x) for x in input().split()]
	even = []
	odd = []
	for num in arr:
		if num % 2 == 0:
			even.append(num)
		else:
			odd.append(num)
	print(*even, *odd)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n):
		if arr[i] % 2 == 1:
			(arr[-1], arr[i]) = (arr[i], arr[-1])
			break
	print(*arr)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	odd = []
	even = []
	for x in arr:
		if x % 2 == 0:
			even.append(x)
		else:
			odd.append(x)
	print(*even, end=' ')
	print(*odd, end=' ')
	print()


from itertools import permutations
t = int(input())
for i in range(t):
	n = int(input())
	nums = list(map(int, input().strip().split()))[0:n:1]
	ans = []
	for i in range(len(nums)):
		if nums[i] % 2 == 0:
			ans.insert(0, nums[i])
		else:
			ans.append(nums[i])
	for i in ans:
		print(i, end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	c = []
	l = list(map(int, input().split()))
	for n in l:
		if n & 1 == 0:
			c.append(n)
	for n in l:
		if n & 1 == 1:
			c.append(n)
	print(*c)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	ar = list(map(int, input().strip().split()))
	res = []
	for n in ar:
		if n & 1 == 0:
			res.append(n)
	for n in ar:
		if n & 1:
			res.append(n)
	print(*res)


t = int(input())
for i in range(t):
	N = int(input())
	(Pos, p) = (list(), list())
	A = [bin(int(x)).lstrip('0b') for x in input().split()]
	for a in range(N):
		if A[a][-1] == '0':
			Pos.append(int(A[a], 2))
		else:
			p.append(int(A[a], 2))
	Pos.extend(p)
	for k in Pos:
		print(k, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	val = list(map(int, input().split()))
	even = []
	odd = []
	for i in val:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	res = even + odd
	for i in range(len(res)):
		print(res[i], end=' ')
	print()


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	odd = []
	even = []
	for i in A:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	s = ''
	e = 0
	o = 0
	for i in range(N):
		if e < len(even):
			s += str(even[e]) + ' '
			e += 1
		else:
			s += str(odd[o]) + ' '
			o += 1
	print(s, flush=True)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	o = []
	for i in l:
		if not i & 1:
			o.append(i)
	for i in l:
		if i & 1:
			o.append(i)
	print(*o)


def binaryForm(num, s):
	if s.get(num):
		return s.get(num)
	result = []
	while num > 0:
		result.append(str(num % 2))
		num = num // 2
	result.reverse()
	return ''.join(result)

def convertListIntoDecimal(result):
	for r in result:
		print(r, end=' ')

def convertIntoBinary(s, numbers):
	category_one = []
	category_two = []
	result = []
	d = {}
	for i in range(len(numbers)):
		if numbers[i] % 2 == 0:
			category_one.append(numbers[i])
		else:
			category_two.append(numbers[i])
	for k in category_one:
		result.append(k)
	for l in category_two:
		result.append(l)
	convertListIntoDecimal(result)
t = int(input())
s = {}
for i in range(t):
	n = int(input())
	numbers = [int(x) for x in input().split()]
	convertIntoBinary(s, numbers)
	print()


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	(odd, even) = ([], [])
	for i in l:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	for i in even:
		print(i, end=' ')
	for i in odd:
		print(i, end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(ans1, ans2) = ([], [])
	for i in l:
		if i % 2 == 0:
			ans1.append(i)
		else:
			ans2.append(i)
	ans = ans1 + ans2
	for i in ans:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	m = input()
	arr = list(map(int, input().split()))
	l = []
	for i in arr:
		l.append(bin(i)[2:])
	ans = []
	for i in range(len(l)):
		if str(l[i])[-1] == '0':
			ans.append(l[i])
			l[i] = -1
	for i in l:
		if i != -1:
			ans.append(i)
	for i in range(len(ans)):
		ans[i] = int(ans[i], 2)
	for i in ans:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = []
	n = []
	for i in l:
		if i % 2 == 0:
			m.append(i)
		else:
			n.append(i)
	ans = m + n
	print(*ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(' '.join((str(x) for x in a if x % 2 == 0)), ' '.join((str(x) for x in a if x % 2)))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = map(int, input().split())
	even = []
	odd = []
	for el in arr:
		if el % 2 == 0:
			even.append(el)
		else:
			odd.append(el)
	e = 0
	o = 0
	e_len = len(even)
	o_len = len(odd)
	even.sort()
	odd.sort(reverse=True)
	for i in range(n):
		if e != e_len:
			print(even[e], end=' ')
			e += 1
		elif o != o_len:
			print(odd[o], end=' ')
			o += 1
	print()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	e = []
	o = []
	for i in a:
		if i % 2 == 0:
			e.append(i)
		else:
			o.append(i)
	print(*e + o)


t = int(input())
for i in range(t):
	z = []
	o = []
	n = int(input())
	l = list(map(int, input().split()))
	for j in range(len(l)):
		if l[j] % 2 == 0:
			z.append(l[j])
		else:
			o.append(l[j])
	z = z + o
	print(*z)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	even = []
	odd = []
	for i in l:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	even += odd
	print(' '.join(map(str, even)))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l1 = []
	l2 = []
	for i in range(n):
		if a[i] % 2 == 0:
			l1.append(a[i])
		else:
			l2.append(a[i])
	for i in range(len(l1)):
		print(l1[i], end=' ')
	for j in range(len(l2)):
		print(l2[j], end=' ')
	print()


def test_case():
	n = int(input())
	a = [int(s) for s in input().split()]
	a.sort(key=lambda x: x & 1)
	a = [str(s) for s in a]
	print(' '.join(a))
t = int(input())
for _ in range(t):
	test_case()


import numpy as np
T = int(input())
for ___ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	o = []
	z = []
	for _ in a:
		if bin(_)[-1] == '0':
			z.append(_)
		else:
			o.append(_)
	for _ in z:
		print(_, end=' ')
	for _ in o:
		print(_, end=' ')
	print()


from sys import stdin

def min_ugly():
	stdin.readline()
	Astr = stdin.readline().strip()
	if Astr[-1] in '13579':
		return Astr
	Ays = Astr.split()
	for (ax, a) in enumerate(Ays):
		if a[-1] in '13579':
			Ays[ax] = Ays[-1]
			Ays[-1] = a
			return ' '.join(Ays)
	return Astr
T = int(stdin.readline())
print(*(min_ugly() for tx in range(T)), sep='\n')


def fun(a):
	i = 0
	j = len(a) - 1
	while i < j:
		while a[i] % 2 == 0 and i < j:
			i += 1
		while a[j] % 2 != 0 and i < j:
			j -= 1
		if i < j:
			(a[i], a[j]) = (a[j], a[i])
			i += 1
			j -= 1
t = int(input())
for i in range(t):
	n = int(input())
	s = ''
	a = list(map(int, input().split()))
	fun(a)
	a = list(map(str, a))
	print(' '.join(a))


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().strip().split()))
	for i in range(n):
		if arr[i] % 2 == 1:
			(arr[i], arr[n - 1]) = (arr[n - 1], arr[i])
			break
	for i in range(n):
		print(arr[i], end=' ')
	print()
	t = t - 1


try:
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		el = []
		ol = []
		for i in l:
			if i % 2 == 0:
				el.append(i)
			else:
				ol.append(i)
		el = el + ol
		print(*el)
except:
	pass


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	even = []
	odd = []
	for i in a:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	res = even + odd
	print(' '.join(map(str, res)))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	left = 0
	right = n - 1
	while left < right:
		while arr[left] % 2 == 0 and left < right:
			left += 1
		while arr[right] % 2 == 1 and left < right:
			right -= 1
		if left < right:
			(arr[left], arr[right]) = (arr[right], arr[left])
			left += 1
			right = right - 1
	print(*arr)


T = int(input())
for i in range(0, T):
	N = int(input())
	arr = input().split(' ')
	even = list()
	odd = list()
	for j in range(0, N):
		if int(arr[j]) % 2 == 0:
			even.append(arr[j])
		else:
			odd.append(arr[j])
	result = even + odd
	print(*result)


n = int(input())
for i in range(n):
	n1 = int(input())
	l2 = []
	l3 = []
	l4 = []
	l1 = list(map(int, input().split(' ')))
	for j in l1:
		if j % 2 == 0:
			l2.append(j)
		else:
			l3.append(j)
	l4 = l2 + l3
	for k in l4:
		print(k, end=' ')
	print('\t')
	l2 = []
	l3 = []
	l4 = []


T = int(input())
for _ in range(T):
	a = []
	b = []
	c = []
	N = int(input())
	arr = input().split(' ')
	arr = [int(x) for x in arr]
	for i in range(N):
		if arr[i] % 2 == 0:
			b.append(arr[i])
		else:
			c.append(arr[i])
	for i in b:
		print(i, end=' ')
	for i in c:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = ['None'] * n
	c = 0
	for i in range(n):
		if l[i] % 2 == 0:
			a[c] = l[i]
			c += 1
	for i in range(n):
		if l[i] % 2 != 0:
			a[c] = l[i]
			c += 1
	for i in range(n):
		print(a[i], end=' ')
	print()


try:
	for i in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		le = []
		lo = []
		for i in range(n):
			if l[i] % 2 == 0:
				le.append(l[i])
			else:
				lo.append(l[i])
		for i in range(len(le)):
			print(le[i], end=' ')
		for i in range(len(lo)):
			print(lo[i], end=' ')
		print()
except:
	pass


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	idx = -1
	for i in range(len(arr)):
		if arr[i] % 2 != 0:
			idx = i
			break
	if idx == -1:
		for i in arr:
			print(i, end=' ')
	else:
		(arr[idx], arr[n - 1]) = (arr[n - 1], arr[idx])
		for i in arr:
			print(i, end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	s = [int(i) for i in input().split()]
	x = []
	l = list(filter(lambda x: x % 2 == 0, s))
	x.extend(l)
	l = list(filter(lambda x: x % 2, s))
	x.extend(l)
	x = list(map(str, x))
	print(' '.join(x))


a = int(input())
for j in range(0, a):
	N = int(input())
	A = list(map(int, input().split()))
	l1 = []
	l2 = []
	for i in A:
		if i % 2 == 0:
			l1.append(i)
		else:
			l2.append(i)
	for k in l1:
		print(k, end=' ')
	for k in l2:
		print(k, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	e = []
	o = []
	for i in range(0, n):
		if l[i] % 2 == 0:
			e.append(l[i])
		else:
			o.append(l[i])
	for i in range(0, len(e)):
		print(e[i], end=' ')
	for i in range(0, len(o)):
		print(o[i], end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	zero = []
	ones = []
	for i in range(n):
		b = bin(arr[i])[2:]
		if b[-1] == '0':
			zero.append(arr[i])
		else:
			ones.append(arr[i])
	ans = zero + ones
	print(*ans)


t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	for i in range(n):
		if li[i] % 2 == 0:
			print(li[i], end=' ')
	for i in range(n):
		if li[i] % 2 == 1:
			print(li[i], end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	odds = []
	evens = []
	for ele in arr:
		if ele & 1:
			odds.append(ele)
		else:
			evens.append(ele)
	odds.sort()
	evens.sort()
	for ele in evens:
		print(ele, end=' ')
	for ele in odds:
		print(ele, end=' ')
	print()


from itertools import permutations as per
from math import factorial as fact
t = int(input())
for _ in range(t):
	n = input()
	a = list(map(int, input().rstrip().split()))
	s = ''
	for i in a:
		if i % 2 == 0:
			print(i, end=' ')
	for i in a:
		if i % 2 != 0:
			print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	temp1 = []
	temp2 = []
	final = []
	for i in range(n):
		if arr[i] % 2 == 0:
			temp1.append(arr[i])
		else:
			temp2.append(arr[i])
	m = len(temp1)
	n = len(temp2)
	if m > n:
		temp = m - n
		for x in range(temp):
			final.append(temp1[-(x + 1)])
		i = n - 1
		j = n - 1
	else:
		i = m - 1
		j = n - 1
	while i >= 0 and j >= 0:
		final.append(temp1[i])
		final.append(temp2[j])
		i -= 1
		j -= 1
	while i >= 0:
		final.append(temp1[i])
		i -= 1
	while j >= 0:
		final.append(temp2[j])
		j -= 1
	print(*final)