Sayaka Saeki is a member of the student council, which has $n$ other members (excluding Sayaka). The $i$-th member has a height of $a_i$ millimeters.

It's the end of the school year and Sayaka wants to take a picture of all other members of the student council. Being the hard-working and perfectionist girl as she is, she wants to arrange all the members in a line such that the amount of photogenic consecutive pairs of members is as large as possible.

A pair of two consecutive members $u$ and $v$ on a line is considered photogenic if their average height is an integer, i.e. $\frac{a_u + a_v}{2}$ is an integer.

Help Sayaka arrange the other members to maximize the number of photogenic consecutive pairs.


-----Input-----

The first line contains a single integer $t$ ($1\le t\le 500$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2000$)  — the number of other council members.

The second line of each test case contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 2 \cdot 10^5$)  — the heights of each of the other members in millimeters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.


-----Output-----

For each test case, output on one line $n$ integers representing the heights of the other members in the order, which gives the largest number of photogenic consecutive pairs. If there are multiple such orders, output any of them.


-----Examples-----

Input
4
3
1 1 2
3
1 1 1
8
10 9 13 15 3 16 9 13
2
18 9
Output
1 1 2 
1 1 1 
13 9 13 15 3 9 16 10 
9 18


-----Note-----

In the first test case, there is one photogenic pair: $(1, 1)$ is photogenic, as $\frac{1+1}{2}=1$ is integer, while $(1, 2)$ isn't, as $\frac{1+2}{2}=1.5$ isn't integer.

In the second test case, both pairs are photogenic.

Difficulty: EASY
Tags: Constructive algorithms

Starter code:

Solutions:
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = [int(i) for i in input().split()][:n]
	b = []
	c = []
	for j in range(n):
		if a[j] % 2 == 0:
			b.append(a[j])
		else:
			c.append(a[j])
	ans = c + b
	ans1 = ' '.join([str(l) for l in ans])
	print(ans1)


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


def func():
	t = int(input())
	for _ in range(t):
		_ = int(input())
		lst = map(int, input().strip().split())
		lst = sorted(lst, key=lambda el: el % 2)
		print(' '.join(map(str, lst)))
func()


for _ in range(int(input())):
	members = int(input())
	heigt = list(map(int, input().split()))
	u_g = [x for x in heigt if x % 2 != 0]
	g = [x for x in heigt if x % 2 == 0]
	print(*u_g, *g)


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		ans1 = []
		ans2 = []
		for item in arr:
			if item % 2 == 0:
				ans2.append(item)
			else:
				ans1.append(item)
		print(*ans1, end=' ')
		print(*ans2)

def nouse0():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse1():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse2():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def nouse3():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse4():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse5():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
main()


n = int(input())
while n:
	input()
	nums = []
	for i in map(int, input().split(' ')):
		if i % 2:
			nums += [i]
		else:
			nums = [i] + nums
	print(' '.join(map(str, nums)))
	n -= 1


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


for i in range(int(input())):
	n = int(input())
	x = [int(x) for x in input().split()]
	l = []
	for i in range(len(x)):
		if x[i] % 2 == 0:
			l.append(x[i])
		else:
			l.reverse()
			l.append(x[i])
			l.reverse()
	print(' '.join(list(map(str, l))))


k = int(input())
for ki in range(k):
	n = int(input())
	my_str_list = input().split()
	my_list = []
	for i in range(n):
		my_list.append(int(my_str_list[i]))
	even_string = ''
	odd_string = ''
	for i in range(n):
		if my_list[i] % 2 == 0:
			even_string += str(my_list[i]) + ' '
		else:
			odd_string += str(my_list[i]) + ' '
	print(even_string + odd_string)


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


for iii in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	w = []
	e = []
	for i in q:
		if i % 2 == 0:
			w.append(i)
		else:
			e.append(i)
	w = w + e
	for i in w:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	(l1, l2) = ([], [])
	for i in l:
		if i % 2 == 1:
			l1.append(i)
		else:
			l2.append(i)
	print(*l1 + l2)


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import sys
input = sys.stdin.readline
M = mod = 998244353

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
for _ in range(val()):
	n = val()
	l = li()
	l.sort(key=lambda x: x & 1)
	print(*l)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	j = n - 1
	while i < j:
		if l[i] % 2 == 0 and l[j] % 2 == 1:
			(l[i], l[j]) = (l[j], l[i])
			i += 1
			j -= 1
		elif l[i] % 2 == 1:
			i += 1
		elif l[j] % 2 == 0:
			j -= 1
	print(*l)


import os
from io import BytesIO, IOBase
import sys
import math

def main():
	for i in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b1 = []
		b2 = []
		even = 0
		for j in range(n):
			if a[j] % 2 == 0:
				b1.append(a[j])
				even = even + 1
			else:
				b2.append(a[j])
		b = []
		for j in range(even):
			b.append(b1[j])
		for j in range(n - even):
			b.append(b2[j])
		print(' '.join(map(str, b)))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
	n = input()
	O = []
	E = []
	A = map(int, input().split())
	for a in A:
		if a % 2 == 0:
			E.append(a)
		else:
			O.append(a)
	ans = O + E
	print(*ans)


T = int(input())
while T > 0:
	N = int(input())
	list1 = [int(x) for x in input().split()]
	odds = []
	evens = []
	final = []
	for i in list1:
		if i % 2 == 0:
			evens.append(i)
		else:
			odds.append(i)
	if len(odds) >= len(evens):
		final.extend(odds)
		final.extend(evens)
	else:
		final.extend(evens)
		final.extend(odds)
	for i in final:
		print(i, end=' ')
	print()
	T -= 1


t = int(input())
for q in range(t):
	n = int(input())
	A = []
	for w in input().split():
		w = int(w)
		if w % 2 == 0:
			A.append(w)
		else:
			A.insert(0, w)
	print(*A)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = -1
	for j in range(0, n):
		if a[j] % 2 == 0:
			d = d + 1
			temp = a[j]
			a[j] = a[d]
			a[d] = temp
	print(*a)


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	A = []
	B = []
	for i in s:
		if i % 2:
			A += [i]
		else:
			B += [i]
	print(*A, end=' ')
	print(*B)


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


def solve(n, a):
	e = []
	o = []
	for i in range(n):
		if a[i] % 2 == 0:
			e.append(a[i])
		else:
			o.append(a[i])
	return ' '.join(map(str, e + o))
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(n, a))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	new = []
	for i in arr:
		if i % 2:
			new.insert(0, i)
		else:
			new.append(i)
	print(*new)


import sys

def readInts():
	return [int(x) for x in sys.stdin.readline().split()]

def readInt():
	return int(sys.stdin.readline())

def segregateEvenOdd(arr, n):
	(left, right) = (0, n - 1)
	while left < right:
		while arr[left] % 2 == 0 and left < right:
			left += 1
		while arr[right] % 2 != 0 and left < right:
			right -= 1
		if left < right:
			(arr[left], arr[right]) = (arr[right], arr[left])
			left += 1
			right = right - 1

def solve():
	n = readInt()
	a = readInts()
	segregateEvenOdd(a, n)
	for i in a:
		print(i, end=' ')
	print()

def main():
	t = readInt()
	for _ in range(t):
		solve()
main()


def AvgHeight(n, l):
	a = [0 for i in range(n)]
	j = 0
	x = n - 1
	for i in range(n):
		if j > x:
			break
		elif l[i] % 2 != 0:
			a[j] = l[i]
			j += 1
		else:
			a[x] = l[i]
			x -= 1
	for i in range(n):
		print(a[i], end=' ')
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	AvgHeight(n, l)


t = int(input())
while t:
	n = int(input())
	s = input().strip().split()
	s = [int(s[i]) for i in range(len(s))]
	odd = [s[i] for i in range(len(s)) if s[i] & 1 == 1]
	even = [s[i] for i in range(len(s)) if s[i] & 1 == 0]
	odd.sort(reverse=True)
	even.sort()
	for i in range(len(odd)):
		print(odd[i], end=' ')
	for i in range(len(even)):
		print(even[i], end=' ')
	print()
	t = t - 1


for _ in range(int(input())):
	input()
	l = list(map(int, input().split()))
	l.sort(key=lambda x: x % 2 == 1)
	print(*l, sep=' ')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(j) for j in input().split()]
	ans = []
	for x in arr:
		if x % 2 == 0:
			ans += [x]
	for x in arr:
		if x % 2 == 1:
			ans += [x]
	print(*ans)


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


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


k = int(input())
for _ in range(k):
	n = int(input())
	a = list(map(int, input().split()))
	chet = ''
	nechet = ''
	for i in range(n):
		if a[i] % 2 == 0:
			chet += f'{a[i]} '
		else:
			nechet += f'{a[i]} '
	print(nechet + chet)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	o = []
	e = []
	for i in range(len(l)):
		if l[i] % 2 == 0:
			e.append(l[i])
		else:
			o.append(l[i])
	f = []
	for i in range(len(o)):
		f.append(o[i])
	for j in range(len(e)):
		f.append(e[j])
	print(*f)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for i in range(n):
		if a[i] % 2 == 0:
			b.append(a[i])
	for i in range(n):
		if a[i] % 2:
			b.append(a[i])
	print(*b)


t = int(input())
for _ in range(t):
	n1 = int(input())
	for i in range(1, 10):
		continue
	arr2 = list(map(int, input().split()))
	even = []
	odd = []
	for i in range(n1):
		if arr2[i] % 2 == 0:
			even.append(arr2[i])
		else:
			odd.append(arr2[i])
	res = []
	for i in range(1, 10):
		continue
	if len(even) >= len(odd):
		res.extend(even)
		res.extend(odd)
	else:
		res.extend(odd)
		res.extend(even)
	for i in range(1, 10):
		continue
	print(*res)


import math, sys, itertools
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
for t in [wtf[i:i + 2] for i in range(1, len(wtf), 2)]:
	n = int(t[0])
	A = list(map(int, t[1].split()))
	O = []
	E = []
	for a in A:
		if a % 2 > 0:
			O.append(a)
		else:
			E.append(a)
	print(' '.join(map(str, O)) + ' ' + ' '.join(map(str, E)))


for _ in range(int(input())):
	(n, y) = (int(input()), sorted(input().split(), key=lambda x: int(x) % 2))
	print(*y)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	l2 = []
	for i in l:
		if i % 2:
			l1.append(i)
		else:
			l2.append(i)
	l1.extend(l2)
	print(' '.join(list(map(str, l1))))


i = 0
a = int(input())
while i < a:
	b = int(input())
	c = input().split(' ')
	d = []
	s = 0
	while s < b:
		if int(c[s]) % 2 == 1:
			d.append(int(c[s]))
		s = s + 1
	s = 0
	while s < b:
		if int(c[s]) % 2 == 0:
			d.append(int(c[s]))
		s = s + 1
	print(*d, sep=' ')
	i = i + 1


def avg_int(a, b):
	return 2 * ((a + b) // 2) == a + b
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = map(int, input().strip().split())
	(odds, evens) = ([], [])
	for e in a:
		if e % 2 == 0:
			evens.append(e)
		else:
			odds.append(e)
	i = 0
	for e in odds:
		i += 1
		print(e, end=' ')
	for e in evens:
		i += 1
		if i == n:
			print(e, end='\n')
		else:
			print(e, end=' ')


from collections import deque, defaultdict, Counter, OrderedDict
from sys import stdin, stdout
import bisect
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
from collections import Counter
from math import sqrt
import collections
import math
import heapq
import re
from statistics import mode

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def modinv(n, p):
	return pow(n, p - 2, p)

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())

def Divisors(n):
	l = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n // i == i:
				l.append(i)
			else:
				l.append(i)
				l.append(n // i)
	return l

def most_frequent(list):
	return max(set(list), key=list.count)

def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def ncr(n, r):
	return fact[n] * pow(fact[r] * fact[n - r], mod - 2, mod) % mod

def Convert(string):
	li = list(string.split(''))
	return li

def SieveOfEratosthenes(n):
	global prime
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	f = []
	for p in range(2, n):
		if prime[p]:
			f.append(p)
	return f
prime = []
q = []

def dfs(n, d, v, c):
	global q
	v[n] = 1
	x = d[n]
	q.append(n)
	j = c
	for i in x:
		if i not in v:
			f = dfs(i, d, v, c + 1)
			j = max(j, f)
	return j

def segregateEvenOdd(arr):
	(left, right) = (0, len(arr) - 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

def main():
	for _ in range(inin()):
		n = inin()
		arr = ain()
		segregateEvenOdd(arr)
		print(*arr)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for i in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	e = []
	o = []
	for i in h:
		if i % 2 == 0:
			e.append(i)
		else:
			o.append(i)
	result = e + o
	for i in range(n):
		if i != n - 1:
			print(result[i], end=' ')
		else:
			print(result[i], end='\n')


for s in [*open(0)][2::2]:
	print(*sorted(s.split(), key=lambda x: int(x) & 1))


T = int(input())
for t in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	ans = []
	for i in arr:
		if i % 2:
			ans.append(i)
	for i in arr:
		if i % 2 == 0:
			ans.append(i)
	print(' '.join(list(map(str, ans))))


for _ in range(int(input())):
	int(input())
	arr = list(map(int, input().split()))
	odd = [x for x in arr if x % 2 == 1]
	even = [x for x in arr if x % 2 == 0]
	print(*odd + even)


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


t = int(input())
for case in range(1, t + 1):
	n = int(input())
	a = list(map(int, input().split()))
	ret = [o for o in a if o % 2 == 1] + [e for e in a if e % 2 == 0]
	print(' '.join([str(v) for v in ret]))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = map(int, input().split())
	even_arr = []
	odd_arr = []
	for i in arr:
		if i % 2 == 0:
			even_arr.append(i)
		else:
			odd_arr.append(i)
	odd_length = len(odd_arr)
	even_length = len(even_arr)
	(i, j) = (0, 0)
	while i < odd_length:
		print(odd_arr[i], end=' ')
		i += 1
	while j < even_length:
		print(even_arr[j], end=' ')
		j += 1


n = int(input())
m = []
for i in range(n):
	a = int(input())
	nums = input().split()
	z = []
	zz = 0
	f = []
	ff = 0
	for j in range(a):
		if int(nums[j]) % 2 == 0:
			z.append(nums[j])
			zz += 1
		else:
			f.append(nums[j])
			ff += 1
	r = []
	if ff >= zz:
		r.extend(f)
		r.extend(z)
	else:
		r.extend(z)
		r.extend(f)
	m.append(r)
for i in range(n):
	for j in range(len(m[i])):
		print(m[i][j], end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	b = []
	arr = list(map(int, input().split()))
	for i in range(n):
		if arr[i] % 2 == 1:
			print(arr[i], end=' ')
		else:
			b.append(arr[i])
	print(*b)


def func(a):
	return a % 2
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(key=func)
	for i in range(n):
		print(arr[i], end=' ')
	print('')


T = int(input())
for i in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	l = []
	l1 = []
	for i in range(N):
		if a[i] % 2 == 0:
			l1.append(a[i])
		else:
			l.append(a[i])
	print(*l, *l1)


t = int(input())
r = []
for i in range(t):
	r.clear()
	n = int(input())
	a = [int(x) for x in input().split()]
	a1 = [int(x) for x in a if x % 2 != 0]
	a2 = [int(x) for x in a if x % 2 == 0]
	r.extend(a1)
	r.extend(a2)
	print(' '.join(map(str, r)))


def sum(m):
	x = []
	y = []
	for j in range(len(m)):
		if m[j] % 2 != 0:
			x.append(m[j])
		else:
			y.append(m[j])
	p = x + y
	q = y + x
	if len(x) == len(y):
		print(*p)
	elif len(x) > len(y):
		print(*p)
	else:
		print(*q)
for t in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	sum(m)


tst = int(input())
while tst:
	n = int(input())
	s = list(map(int, input().split()))
	ans = []
	for i in s:
		if i % 2 != 0:
			ans.insert(0, i)
		else:
			ans.append(i)
	print(*ans)
	tst -= 1


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
test_case = inp()
current_test = 0
while current_test < test_case:
	current_test += 1
	n = inp()
	lst = inlt()
	odd_numbers = [number for number in lst if number % 2 == 1]
	even_numbers = [numbers for numbers in lst if numbers % 2 == 0]
	a = odd_numbers + even_numbers
	b = ''
	for i in a:
		b += f'{i} '
	print(b)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	o = list((i for i in a if i % 2 != 0))
	e = list((i for i in a if i % 2 == 0))
	x = o + e
	for i in x:
		print(i, end=' ')
	print()


sagnik = int(input())
while sagnik != 0:
	sagnik -= 1
	n = int(input())
	a = list(map(int, input().split()))
	(odd, ev) = ([], [])
	for i in a:
		if i & 1:
			odd.append(i)
		else:
			ev.append(i)
	for i in odd:
		print(i, end=' ')
	print(*ev)


t = int(input())
for i in range(t):
	n = int(input())
	ev = list()
	od = list()
	a = list(map(int, input().strip().split()))[:n]
	for x in range(n):
		if a[x] % 2:
			od.append(a[x])
		else:
			ev.append(a[x])
		le = int(len(ev))
		lo = int(len(od))
	res = list()
	for j in range(le):
		res.append(ev[j])
	for j in range(lo):
		res.append(od[j])
	print(*res)


import sys, math
from collections import deque, defaultdict
import operator as op
from functools import reduce
from itertools import permutations
I = sys.stdin.readline
alpha = 'abcdefghijklmnopqrstuvwxyz'

def ii():
	return int(I().strip())

def li():
	return list(map(int, I().strip().split()))

def mi():
	return map(int, I().strip().split())

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def isPrime(n):
	if n <= 1:
		return False
	elif n <= 2:
		return True
	else:
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

def main():
	ans = ''
	for _ in range(ii()):
		n = ii()
		arr = li()
		i = 0
		j = 0
		while j < n:
			if arr[j] % 2:
				(arr[i], arr[j]) = (arr[j], arr[i])
				i += 1
			j += 1
		print(*arr)
main()


n = int(input())
t = []
for i in range(n):
	x = int(input())
	y = list(map(int, input().split()))
	t.append(y)
for k in t:
	o = ''
	e = ''
	for l in range(len(k)):
		if k[l] % 2 == 0:
			e += str(k[l]) + ' '
		else:
			o += str(k[l]) + ' '
	print(o + e)


from collections import Counter
from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	n = int(input())
	x = list(map(int, stdin.readline().split()))
	l = []
	for i in range(n):
		if x[i] % 2 != 0:
			l.append(x[i])
	for i in range(n):
		if x[i] % 2 == 0:
			l.append(x[i])
	print(*l)


from collections import deque
t = int(input(''))
for i in range(t):
	n = int(input(''))
	a = list(map(int, input().split()))
	queue = deque([])
	for i in range(n):
		if a[i] % 2 == 0:
			queue.append(a[i])
		else:
			queue.appendleft(a[i])
	ans = ''
	for i in range(n):
		ans += str(queue[i]) + ' '
	print(ans[0:len(ans) - 1])


t = int(input())
for z in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	odd = []
	even = []
	for num in arr:
		if num % 2 == 0:
			even.append(num)
		else:
			odd.append(num)
	c = odd + even
	print(*c)


t = int(input())
for i in range(t):
	n = int(input())
	h = [int(j) for j in input().split()]
	o = []
	e = []
	for it in h:
		if it % 2 != 0:
			o.append(it)
		else:
			e.append(it)
	for it in o:
		print(it, end=' ')
	for it in e:
		print(it, end=' ')


from sys import stdin, stdout
get_string = lambda : stdin.readline().strip(' ')
get_intmap = lambda : map(int, get_string().split(' '))

def testcase():
	n = int(input())
	l = tuple(get_intmap())
	odds = [str(i) for i in l if i % 2 == 1]
	even = [str(i) for i in l if i % 2 == 0]
	print(' '.join(odds + even))
for t in range(int(input())):
	testcase()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(key=lambda x: x % 2)
	print(*arr)


my_value = []
for i in range(int(input())):
	num = int(input())
	lis = list(map(int, input().split()))
	lis_even = []
	lis_odd = []
	for i in lis:
		if i % 2 == 0:
			lis_even.append(i)
		else:
			lis_odd.append(i)
	my_value.append(lis_odd + lis_even)
for i in my_value:
	print(*i)


for i in range(int(input())):
	d = int(input())
	li = list(map(int, input().split()))
	a = []
	b = []
	for j in li:
		if j % 2 == 0:
			a.append(j)
		else:
			b.append(j)
	for k in a:
		print(k, end=' ')
	for f in b:
		print(f, end=' ')


import sys
input = sys.stdin.readline
from collections import defaultdict as dc
from collections import Counter
from bisect import bisect_right, bisect_left
import math
from operator import itemgetter
from heapq import heapify, heappop, heappush
from queue import PriorityQueue as pq
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = []
	q = []
	for i in l:
		if i % 2:
			p.append(i)
		else:
			q.append(i)
	p = p + q
	print(*p)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	o = []
	e = []
	for j in range(len(l)):
		if l[j] % 2 == 1:
			o.append(l[j])
		if l[j] % 2 == 0:
			e.append(l[j])
	l1 = o + e
	print(' '.join((repr(e) for e in l1)))


import random
from collections import Counter as cc
from copy import deepcopy as dc
try:
	t = int(input())
	while t:
		n = int(input())
		a = list(map(int, input().split()))
		(odd, even) = ([], [])
		for i in a:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		odd = odd + even
		print(*odd)
		t -= 1
except EOFError as e:
	pass


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	ans = []
	for a in arr:
		if a % 2 == 0:
			ans.append(a)
	for a in arr:
		if a % 2 != 0:
			ans.append(a)
	print(*ans)


import sys
readline = sys.stdin.readline
n = int(readline())
for i in range(n):
	num = int(readline())
	lis = list(map(int, input().split()))
	elis = []
	olis = []
	for j in lis:
		if j % 2 == 0:
			elis.append(j)
		else:
			olis.append(j)
	lis = []
	lis = elis + olis
	print(*lis)


t = int(input())
while t > 0:
	t = t - 1
	A = int(input())
	arry = map(int, input().split())
	mni = list(arry)
	evenlist = []
	oddlist = []
	for i in range(A):
		if mni[i] % 2 == 0:
			evenlist.append(mni[i])
		else:
			oddlist.append(mni[i])
	print(*oddlist + evenlist)


for _ in range(int(input())):
	_ = input()
	values = list(map(int, input().split()))
	(odd, even) = ([], [])
	for x in values:
		if x % 2:
			odd.append(x)
		else:
			even.append(x)
	print(' '.join(map(str, odd + even)))


import os
import sys
from io import BytesIO, IOBase
import math
from queue import Queue
import itertools
import bisect
import heapq

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	return l

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)

def countcon(s, i):
	c = 0
	ch = s[i]
	for i in range(i, len(s)):
		if s[i] == ch:
			c += 1
		else:
			break
	return c

def lis(arr):
	n = len(arr)
	lis = [1] * n
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and lis[i] < lis[j] + 1:
				lis[i] = lis[j] + 1
	maximum = 0
	for i in range(n):
		maximum = max(maximum, lis[i])
	return maximum

def isSubSequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def maxfac(n):
	root = int(n ** 0.5)
	for i in range(2, root + 1):
		if n % i == 0:
			return n // i
	return n

def p2(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def seive(n):
	primes = [True] * (n + 1)
	primes[1] = primes[0] = False
	for i in range(2, n + 1):
		if primes[i]:
			for j in range(i + i, n + 1, i):
				primes[j] = False
	p = []
	for i in range(0, n + 1):
		if primes[i]:
			p.append(i)
	return p

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def denofactinverse(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return pow(fac, m - 2, m)

def numofact(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return fac

def sod(n):
	s = 0
	while n > 0:
		s += n % 10
		n //= 10
	return s
for xyz in range(0, int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(o, e) = ([], [])
	for i in l:
		if i % 2:
			o.append(i)
		else:
			e.append(i)
	print(*o, *e)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	lst1 = []
	for a in lst:
		if a % 2 == 1:
			lst1.insert(0, a)
		else:
			lst1.append(a)
	print(*lst1)


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


t = int(input())
for i in range(t):
	n = int(input())
	line = input()
	nums = line.split()
	evenpair = []
	oddpair = []
	for num in nums:
		num = int(num)
		if num % 2 == 0:
			evenpair.append(num)
			continue
		oddpair.append(num)
	out = ''
	for num in evenpair:
		out += str(num) + ' '
	for num in oddpair:
		out += str(num) + ' '
	print(out[:-1])


import os
import sys
from io import BytesIO, IOBase

def main():
	import bisect
	import math
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
	inf = 1e+17
	mod = 10 ** 9 + 7

	def factorial(n):
		f = 1
		for i in range(1, n + 1):
			f = f * i % mod
		return f

	def ncr(n, r):
		num = den = 1
		for i in range(r):
			num = num * (n - i) % mod
			den = den * (i + 1) % mod
		return num * pow(den, mod - 2, mod) % mod

	def solve(n, arr):
		evens = []
		odds = []
		for i in range(n):
			if arr[i] % 2:
				odds.append(arr[i])
			else:
				evens.append(arr[i])
		evens.sort(reverse=True)
		odds.sort(reverse=True)
		return ' '.join(list(map(str, evens + odds)))
		pass
		pass
	t = int(input())
	ans = []
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ans.append(solve(n, arr))
	for j in range(len(ans)):
		print(ans[j])
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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

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

def check_palindrome(s):
	n = len(s)
	for i in range(n):
		if s[i] != s[n - i - 1]:
			return False
	return True
for ii in range(int(input())):
	n = int(input())
	a = mapIn()
	left = []
	right = []
	for x in a:
		if x % 2:
			left.append(x)
		else:
			right.append(x)
	a = left + right
	for x in a:
		print(x, end=' ')
	print()


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(*sorted(a, key=lambda x: x % 2))


arr = []
test_cases = int(input(''))
for x in range(test_cases):
	notneeded = input()
	a = []
	a = list(map(int, input().split()))
	arr.append(a)
for l in arr:
	even_part = [num for num in l if num % 2 == 0]
	odd_part = [num for num in l if num % 2 != 0]
	print(*odd_part + even_part)


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


for _ in range(int(input())):
	n = int(input())
	arr = map(int, input().split())
	odds = []
	evens = []
	for i in arr:
		if i % 2 != 0:
			odds.append(i)
		else:
			evens.append(i)
	print(*odds + evens)


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


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


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


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	e = []
	o = []
	for i in arr:
		if i % 2:
			o.append(i)
		else:
			e.append(i)
	print(*o + e)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	result = deque()
	for i in range(n):
		if l[i] % 2:
			result.appendleft(l[i])
		else:
			result.append(l[i])
	for i in result:
		print(i, end=' ')
	print()


tc = int(input())
for _ in range(tc):
	n = int(input())
	lis = list(map(int, input().split()))
	lis1 = [x for x in lis if x % 2 == 0]
	lis2 = [x for x in lis if x % 2 == 1]
	lis = lis1 + lis2
	print(*lis)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
readint = lambda : int(sys.stdin.readline().rstrip('\r\n'))
readints = lambda : map(int, sys.stdin.readline().rstrip('\r\n').split())
readstr = lambda : sys.stdin.readline().rstrip('\r\n')
readstrs = lambda : map(str, sys.stdin.readline().rstrip('\r\n').split())
readarri = lambda : [int(_) for _ in sys.stdin.readline().rstrip('\r\n').split()]
readarrs = lambda : [str(_) for _ in sys.stdin.readline().rstrip('\r\n').split()]
mod = 998244353
MOD = int(1000000000.0) + 7

def solve():
	n = readint()
	arr = list(readints())
	od = []
	even = []
	for i in arr:
		if i & 1:
			od.append(str(i))
		else:
			even.append(str(i))
	print(' '.join(od + even))

def main():
	t = 1
	t = readint()
	for _ in range(t):
		solve()
main()


t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	sc = ''
	sl = ''
	for x in a:
		if x % 2 == 0:
			sc += str(x) + ' '
		else:
			sl += str(x) + ' '
	print((sc + sl)[:-1])


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


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	li1 = []
	li2 = []
	for i in li:
		if i % 2 == 0:
			li1.append(i)
		else:
			li2.append(i)
	s = li1 + li2
	for i in s:
		print(i, end=' ')
	print()


t = int(input())

def f(x):
	y = x.split(' ')
	i = 0
	for i in range(len(y)):
		y[i] = int(y[i])
	l1 = []
	l2 = []
	i = 0
	for i in range(len(y)):
		if y[i] % 2 == 0:
			l2 = l2 + [y[i]]
			i += 1
		else:
			l1 = l1 + [y[i]]
			i += 1
	l = l1 + l2
	s = ''
	i = 0
	for i in range(len(l)):
		s += str(l[i]) + ' '
	return s
lines = ''
ans = ''
for i in range(2 * t):
	x = input()
	lines += x + '\n'
	if i % 2 != 0:
		ans += f(x) + '\n'
print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	odd = list(filter(lambda x: x % 2 == 1, a))
	even = list(filter(lambda x: x % 2 == 0, a))
	print(*odd + even)


for _ in range(int(input())):
	input()
	d = []
	[print(i, end=' ') if i % 2 == 1 else d.append(i) for i in [int(i) for i in input().split()]]
	print(*d)


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


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
n = inp()
for i in range(0, n):
	ln = inp()
	l = inlt()
	e = []
	o = []
	f = True
	for k in range(0, ln):
		if l[k] % 2 == 0:
			e.append(l[k])
		else:
			o.append(l[k])
	for k in range(0, len(e)):
		if f is False:
			print(' ', end='')
		f = False
		print(e[k], end='')
	for k in range(0, len(o)):
		if f is False:
			print(' ', end='')
		f = False
		print(o[k], end='')
	print('\n', end='')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	hs = list(map(int, input().split()))
	even = []
	odd = []
	for h in hs:
		if h % 2:
			odd.append(h)
		else:
			even.append(h)
	for x in odd:
		print(x, end=' ')
	for x in even:
		print(x, end=' ')
	print()


from sys import stdin, stdout, setrecursionlimit
input = stdin.readline
INF = float('inf')
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt

def geti():
	return map(int, input().strip().split())

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

def getis():
	return map(str, input().strip().split())

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

def gets():
	return input().strip()

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')

def solve():
	for _ in range(geta()):
		n = geta()
		a = getl()
		odd = []
		even = []
		for i in a:
			if i & 1:
				odd.append(i)
			else:
				even.append(i)
		odd.extend(even)
		print(*odd)
solve()


t = int(input())
a = []
for i in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	li.sort(key=lambda x: (-(x % 2), x))
	b = [str(j) for j in li]
	a.append(b)
for k in range(t):
	print(' '.join(a[k][:]))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans1 = []
	ans2 = []
	for i in arr:
		if i % 2 == 1:
			ans1.append(i)
		else:
			ans2.append(i)
	ans = ans1 + ans2
	print(*ans)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	n = inp()
	l = li()
	c = deque()
	for i in l:
		if i % 2:
			c.appendleft(i)
		else:
			c.append(i)
	print(*c)
for _ in range(inp()):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	j = n - 1
	while i < j:
		if a[i] % 2 == 0 and a[j] % 2 != 0:
			temp = a[i]
			a[i] = a[j]
			a[j] = temp
			i += 1
			j -= 1
		elif a[i] % 2 != 0:
			i += 1
		elif a[j] % 2 == 0:
			j -= 1
		else:
			i += 1
			j -= 1
	print(*a)


x = int(input())
for i in range(x):
	y = int(input())
	z = list(map(int, input().split()))
	m = []
	n = []
	for j in z:
		if j % 2 == 0:
			m.append(j)
		else:
			n.append(j)
	t = n + m
	w = ' '.join(list(map(str, t)))
	print(w)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	ans = list(filter(lambda x: x % 2, a)) + list(filter(lambda x: x % 2 == 0, a))
	print(*ans)

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		solve()
main()


from math import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	odd = []
	ev = []
	n = inp()
	a = lis()
	for i in a:
		if i % 2:
			odd.append(i)
		else:
			ev.append(i)
	odd = odd + ev
	print(*odd)


tst = int(input())
while tst:
	n = int(input())
	s = list(map(int, input().split()))
	odd = []
	even = []
	for i in s:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	print(*odd, *even)
	tst -= 1


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


for _ in range(int(input())):
	no_of_members = int(input())
	heights = list(map(int, input().split()))
	(odds, evens) = ([], [])
	for i in heights:
		if i % 2 == 0:
			evens.append(str(i))
		else:
			odds.append(str(i))
	print(' '.join(odds + evens))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	kel = [i for i in a if i % 2]
	fel = [i for i in a if i % 2 == 0]
	kelfel = kel + fel
	print(*kelfel)


def row(a):
	l1 = []
	l2 = []
	for i in a:
		if i % 2 == 0:
			l1.append(i)
		else:
			l2.append(i)
	l2 += l1
	for i in l2:
		print(i, end=' ')
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	row(a)
	if i < n:
		print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split(' ')))
	ev = []
	od = []
	for i in l:
		if i % 2 == 0:
			ev.append(i)
		else:
			od.append(i)
	fina = []
	for i in od:
		fina.append(i)
	for i in ev:
		fina.append(i)
	print(*fina)


import sys, math, bisect
inf = float('inf')
input = sys.stdin.readline
mod = 10 ** 9 + 7

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def freq(a, x):
	z = upperBound(a, x) - lowerBound(a, x)
	if z <= 0:
		return 0
	return z
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	even = []
	odd = []
	ans = []
	for i in arr:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	for i in even:
		ans.append(i)
	for i in odd:
		ans.append(i)
	print(*ans)


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	res = []
	for i in range(n):
		if arr[i] % 2 != 0:
			res.append(arr[i])
	for i in range(n):
		if arr[i] % 2 == 0:
			res.append(arr[i])
	print(' '.join((str(i) for i in res)))
	return
t = int(input())
for t in range(t):
	main()


for i in range(int(input())):
	num = input()
	str1 = input().split(' ')
	str1 = list(map(int, str1))
	p = ' '.join(list(map(str, sorted(str1, key=lambda x: x % 2))))
	print(p)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = input().split()
	lst = [int(i) for i in lst]
	gjl = []
	gnp = []
	for i in lst:
		if i % 2 == 0:
			gnp.append(i)
		else:
			gjl.append(i)
	for i in gjl:
		print(i, end=' ')
	for i in gnp:
		print(i, end=' ')
	print()


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


for _ in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()), key=lambda x: x & 1)
	print(*a)


t = int(input())
for _ in range(t):
	n = int(input())
	daf = list(map(int, input().split()))
	daf_odd = [x for x in daf if x % 2]
	daf_even = [x for x in daf if not x % 2]
	daf = daf_odd + daf_even
	print(*daf)


t = int(input())
lan = []
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	l_odd = []
	l_even = []
	ls = []
	for number in x:
		if number % 2 == 0:
			l_even.append(number)
		else:
			l_odd.append(number)
	for number in l_even:
		ls.append(number)
	for number in l_odd:
		ls.append(number)
	lan.append(ls)
for y in lan:
	print(*y, sep=' ')


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


for i in range(int(input())):
	n = int(input())
	arr = [int(_) for _ in input().split()]
	l = []
	for num in arr:
		if num % 2 == 0:
			l.append(num)
	for num in arr:
		if num % 2 != 0:
			l.append(num)
	print(*l)


for t in range(int(input())):
	N = int(input())
	ar = list(map(int, input().split()))
	t1 = []
	t2 = []
	for i in ar:
		if i % 2:
			t1.append(i)
		else:
			t2.append(i)
	print(*t1 + t2)


t = int(input())
for i in range(t):
	n = int(input())
	nums = [int(i) for i in input().split()]
	odds = []
	evens = []
	for i in nums:
		if i % 2 == 1:
			odds.append(i)
		else:
			evens.append(i)
	print(' '.join([str(i) for i in odds]) + ' ' + ' '.join([str(i) for i in evens]))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(odd, even, ans) = ([], [], [])
	for x in a:
		if x % 2 == 1:
			odd.append(x)
		else:
			even.append(x)
	ans = odd + even
	print(*ans)


T = int(input())

def Solve(n, arr):
	ans = []
	for i in range(n):
		if arr[i] % 2 != 0:
			ans.append(arr[i])
	for i in range(n):
		if arr[i] % 2 == 0:
			ans.append(arr[i])
	print(' '.join(map(str, ans)))
for i in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	Solve(n, arr)


for tt in range(int(input())):
	n = int(input())
	(a1, a2) = ([], [])
	for x in list(map(int, input().split())):
		if x % 2:
			a1.append(x)
		else:
			a2.append(x)
	a1 += a2
	print(*a1)


testcases = int(input())
for i in range(testcases):
	n = int(input())
	lst = [int(i) for i in input().split()]
	even = []
	odd = []
	for i in lst:
		if i % 2 == 0:
			even.append(i)
		elif i % 2 != 0:
			odd.append(i)
		lst1 = odd + even
	for i in lst1:
		print(i, end=' ')
	print()


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


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = [i for i in arr if i % 2 == 0]
	arr2 = [i for i in arr if i % 2 != 0]
	arr3 = arr2 + arr1
	print(*arr3)


import math
for t in range(int(input())):
	n = int(input())
	a1 = list(map(int, input().split()))
	odd = []
	even = []
	for k in a1:
		if k % 2 == 0:
			even += [k]
		else:
			odd += [k]
	for e in even:
		print(e, end=' ')
	for o in odd:
		print(o, end=' ')
	print()


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		nums = {0: [], 1: []}
		for i in arr:
			nums[i & 1].append(str(i))
		o = ' '.join(nums[0])
		if o and nums[1]:
			o += ' '
		o += ' '.join(nums[1])
		print(o)
main()


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


list1 = []
for i in range(int(input())):
	n = int(input())
	s = list(sorted(input().split(), key=lambda x: int(x) % 2 == 0))
	list1.append(' '.join(s))
print(*list1, sep='\n')


import os
import sys
from io import BytesIO, IOBase

def main():
	t = int(input())
	for x in range(t):
		n = int(input())
		l = list(map(int, input().split()))
		even = []
		odd = []
		for i in l:
			if i % 2 == 0:
				even += [i]
			else:
				odd += [i]
		even.sort()
		odd.sort()
		for i in range(len(odd) - 1, -1, -1):
			print(odd[i], end=' ')
		for i in range(len(even) - 1, -1, -1):
			print(even[i], end=' ')
		print()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import Counter, deque
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	n = int(input())
	arr = [int(char) for char in input().split()]
	return [a for a in arr if a & 1] + [a for a in arr if not a & 1]
for _ in range(int(input())):
	print(*solve())


def Solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	c = []
	for i in range(len(a)):
		if a[i] % 2 == 0:
			c.append(a[i])
		else:
			b.append(a[i])
	for i in range(len(b)):
		print(b[i], end=' ')
	for i in range(len(c)):
		print(c[i], end=' ')
	print()
q = int(input())
while q:
	Solve()
	q -= 1


tests = int(input())
while tests > 0:
	size = int(input())
	arr = [int(x) for x in input().split()]
	even = []
	odds = []
	for x in arr:
		if x % 2 == 0:
			even.append(x)
		else:
			odds.append(x)
	if len(even) != 0:
		print(*even, end=' ')
	if len(odds) != 0:
		print(*odds)
	tests = tests - 1


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	odd = [str(i) for i in l if i % 2 != 0]
	even = [str(i) for i in l if i % 2 == 0]
	x = odd + even
	print(' '.join(x))


import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	l = inlt()
	odd = []
	even = []
	for each in l:
		if each % 2 == 0:
			even.append(each)
		else:
			odd.append(each)
	print(*odd + even)


import os
import sys
from io import BytesIO, IOBase
_print = print
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def inp():
	return sys.stdin.readline().rstrip()

def mpint():
	return map(int, inp().split(' '))

def itg():
	return int(inp())

def solve():
	n = itg()
	return sorted(mpint(), key=lambda x: x & 1)

def main():
	for _ in range(itg()):
		print(*solve())
DEBUG = 0
URL = 'https://codeforces.com/contest/1509/problem/0'
if DEBUG == 1:
	import requests
	from ACgenerator.Y_Test_Case_Runner import TestCaseRunner
	runner = TestCaseRunner(main, URL)
	inp = runner.input_stream
	print = runner.output_stream
	runner.checking()
else:
	if DEBUG != 2:
		(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	if DEBUG:

		def print(*args, **kwargs):
			_print(*args, **kwargs)
			sys.stdout.flush()
	main()


for _ in range(int(input())):
	n = int(input())
	s = []
	s1 = []
	a = [int(a) for a in input().split()]
	for j in range(n):
		if a[j] % 2 == 1:
			s.append(a[j])
		else:
			s1.append(a[j])
	print(*s + s1)


from queue import deque
tcs = int(input())
for tc in range(tcs):
	n = int(input())
	li = list(map(int, input().split()))
	ans = deque()
	for i in li:
		if i % 2 == 0:
			ans.append(i)
		else:
			ans.appendleft(i)
	print(*ans)


import collections
import itertools
from functools import reduce
mod = 10 ** 9 + 7

def permutationbysum():
	for _ in range(int(input())):
		(num, l, r, achieve) = map(int, input().split())
		k = r - l + 1
		if k * (k + 1) // 2 <= achieve <= k * (num * 2 + 1 - k) // 2:
			outpos = r % num
			inpos = l - 1
			ans = [0] * num
			for i in range(num, 0, -1):
				if achieve - i > 0 or (achieve - i == 0 and inpos == r - 1):
					achieve -= i
					ans[inpos] = i
					inpos += 1
				else:
					ans[outpos] = i
					outpos += 1
					outpos %= num
			print(*ans)
		else:
			print(-1)

def peaks():
	for _ in range(int(input())):
		(num, peak) = map(int, input().split())
		pos = 1
		rpos = num
		ans = []
		now = 0
		if num == 1:
			if not peak:
				print(1)
			else:
				print(-1)
			continue
		if num == 2:
			if peak:
				print(-1)
			else:
				print(1, 2)
			continue
		added = 0
		while rpos + 1 != pos:
			if not peak:
				while pos <= rpos:
					ans.append(pos)
					pos += 1
				break
			if not now:
				ans.append(pos)
				pos += 1
			else:
				ans.append(rpos)
				rpos -= 1
				if num - added != 1:
					peak -= 1
			added += 1
			now = 1 - now
		if peak:
			print(-1)
			continue
		print(*ans)
import sys
input = sys.stdin.readline

def addone():
	for _ in range(int(input())):
		(num, changes) = input().split()
		l = collections.deque(sorted([int(i) for i in num]))
		perm = collections.deque()
		changes = int(changes)
		cd = 0
		ans = len(num)
		while True:
			nextnum = l.pop()
			while perm and perm[-1] == nextnum:
				l.append(perm.pop())
			c = 10 - nextnum - cd
			changes -= c
			cd += c
			if changes >= 0:
				if not c:
					perm.appendleft(1 - cd)
					l.appendleft(-cd)
				else:
					l.appendleft(1 - cd)
					l.appendleft(-cd)
				ans += 1
			else:
				break
		print(ans % 1000000007)
import math

def andsequences():

	def mapping(num):
		nonlocal mnum
		nonlocal c
		num = int(num)
		if num < mnum:
			mnum = num
			c = 1
		elif num == mnum:
			c += 1
		return num
	mod = 1000000007
	for _ in range(int(input())):
		mnum = float('inf')
		c = 0
		num = int(input())
		l = list(map(mapping, input().split()))
		for i in l:
			if mnum & i != mnum:
				print(0)
				break
		else:
			if c == 1:
				print(0)
			else:
				print(math.factorial(num - 2) * (c - 1) * c % mod)

def numberdigit():
	n = 10 ** 5 * 2
	l = [0] * 11
	mod = 10 ** 9 + 7
	l[0] = l[1] = l[2] = l[3] = l[4] = l[5] = l[6] = l[7] = l[8] = 2
	l[9] = 3
	l[10] = 4
	for i in range(11, n):
		l.append((l[i - 10] + l[i - 9]) % mod)
	for _ in range(int(input())):
		(num, c) = input().split()
		c = int(c)
		ans = 0
		for i in num:
			i = int(i)
			if 10 - i > c:
				ans += 1
			else:
				ans += l[c - (10 - i)]
		print(ans % mod)

def mushroom():
	(people, t1, t2, percent) = map(int, input().split())
	l = []
	percent = 1 - percent * 0.01
	for i in range(1, people + 1):
		(s, s1) = map(int, input().split())
		l.append([i, max(s * t1 * percent + s1 * t2, s1 * t1 * percent + s * t2)])
	l.sort(key=lambda x: x[1], reverse=True)
	for i in l:
		i[1] = '{:.2f}'.format(i[1])
		print(*i)

def escape():
	prins = int(input())
	dra = int(input())
	start = int(input())
	pack = int(input())
	c = int(input())
	speeddiff = dra - prins
	if speeddiff <= 0:
		return 0
	pd = start * prins
	ans = 0
	while pd < c:
		hs = pd / speeddiff
		pd += prins * hs
		if pd >= c:
			break
		time = pd / dra
		time += pack
		pd += prins * time
		ans += 1
	return ans

def perm():

	def high(n, k):
		return k * (2 * n - k + 1) // 2

	def low(k):
		return k * (k + 1) // 2
	for _ in range(int(input())):
		(num, lef, rig, s) = map(int, input().split())
		k = rig - lef + 1
		(rig, lef) = (rig - 1, lef - 1)
		if not high(num, k) >= s >= low(k):
			print(-1)
			continue
		l = [0] * num
		lp = lef
		rp = lef - 1
		for i in range(num, 0, -1):
			if high(i, k) >= s and s - i >= low(k - 1) and k:
				l[lp] = i
				lp += 1
				s -= i
				k -= 1
			else:
				l[rp] = i
				rp -= 1
		if k:
			print(-1)
		else:
			print(*l)

def newcom():
	for _ in range(int(input())):
		(days, price) = map(int, input().split())
		dl = input().split()
		worth = input().split()
		worth.append(0)
		ans = float('inf')
		req = 0
		left = 0
		for i in range(days):
			a = int(dl[i])
			w = int(worth[i])
			ans = min(ans, req + max(0, price - left + a - 1) // a)
			ns = max(0, w - left + a - 1) // a
			req += ns + 1
			left += a * ns - w
		print(ans)

def perfectsq():
	for _ in range(int(input())):
		n = input()
		for i in input().split():
			sq = math.sqrt(int(i))
			if sq != int(sq):
				print('YES')
				break
		else:
			print('NO')

def and0big():
	for _ in range(int(input())):
		(l, k) = map(int, input().split())
		print(l ** k % mod)
import math

def mod1p():
	n = int(input())
	ans = dict()
	p = 1
	for i in range(1, n):
		if math.gcd(i, n) == 1:
			ans[str(i)] = True
			p = p * i % n
	if p == 1:
		print(len(ans))
		print(' '.join(ans.keys()))
	else:
		ans.pop(str(p))
		print(len(ans))
		print(' '.join(ans.keys()))

def shorttask():
	num = 10000100
	l = [-1] * (num + 2)
	s = [-1] * (num + 2)
	l[1] = 1
	for i in range(2, int(math.sqrt(num + 1)) + 2):
		if l[i] == -1:
			l[i] = i
			for x in range(i * i, num + 1, i):
				if l[x] == -1:
					l[x] = i
	s[1] = 1
	for i in range(2, num + 1):
		if l[i] == -1:
			l[i] = i
			s[i] = i + 1
		else:
			i1 = i
			s[i] = 1
			while i1 % l[i] == 0:
				i1 //= l[i]
				s[i] = s[i] * l[i] + 1
			s[i] *= s[i1]
	ans = [-1] * (num + 1)
	for i in range(num, 0, -1):
		if s[i] < num:
			ans[s[i]] = i
	for _ in range(int(input())):
		print(ans[int(input())])

def review():
	for _ in range(int(input())):
		n = int(input())
		ans = 0
		for i in input().split():
			i = int(i)
			if i == 1 or i == 3:
				ans += 1
		print(ans)

def GCDleng():
	po10 = [0] * 11
	po10[1] = 1
	for i in range(2, 11):
		po10[i] = po10[i - 1] * 10
	for _ in range(int(input())):
		(n, n1, res) = map(int, input().split())
		print(po10[n], po10[n1] + po10[res])

def anothercarddeck():
	(n, q) = map(int, input().split())
	l = input().split()
	d = {l[i]: i for i in range(n - 1, -1, -1)}
	ans = []
	for i in input().split():
		now = d[i]
		ans.append(now + 1)
		for key in d:
			if d[key] < now:
				d[key] += 1
		d[i] = 0
	print(*ans)

def mincoststring():
	(n, letters) = map(int, input().split())
	l = [chr(i + 97) for i in range(letters)]
	ans = []
	real = letters - 1
	if not n:
		print(*ans, sep='')
		return
	if n == 1:
		print(*ans, sep='', end='')
		print(l[1 % (real + 1)])
		return
	while n:
		for i in range(len(l)):
			for i1 in range(i, len(l)):
				if i1 != real:
					ans.append(l[i1])
					ans.append(l[i])
					n -= 2
				else:
					ans.append(l[i1])
					n -= 1
				if not n:
					print(*ans, sep='')
					return
				if n == 1:
					print(*ans, sep='', end='')
					print(l[(i1 + 1) % (real + 1)])
					return
	print(*ans)

def mincost2():
	(n, letters) = map(int, input().split())
	l = [chr(i + 97) for i in range(letters)]
	comb = []
	if letters == 1 or n == 1:
		print('a' * n)
		return
	for i in range(letters):
		for i1 in range(i, letters):
			comb.append(l[i1] + l[i])
	lc = len(comb)
	while True:
		for i in range(lc):
			if ord(comb[i][0]) - 97 == letters - 1:
				n -= 1
				print(comb[i][0], end='')
			else:
				n -= 2
				print(comb[i], end='')
			if n == 1:
				pos = ord(comb[i][0]) - 97 + 1
				print(l[pos % letters])
				return
			if not n:
				return

def Tittat():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		l = list(map(int, input().split()))
		for i in range(n):
			if not k:
				break
			while k and l[i]:
				l[i] -= 1
				l[-1] += 1
				k -= 1
		print(*l)

def xorq2():
	for _ in range(int(input())):
		n = int(input())
		s = 0
		num = -1
		nc = 0
		c = 0
		for i in input().split():
			i = int(i)
			s ^= i
			c += 1
			if num == -1 and s == i:
				num = s
				s = 0
				nc += c
				c = 0
			if num != -1 and (s == num or not s):
				s = 0
				nc += c
				c = 0
		print(['NO', 'YES'][nc == n])

def xorq2re():
	n = int(input())
	s = input().split()
	xor = 0
	for i in range(n):
		s[i] = int(s[i])
		xor ^= s[i]
	if not xor:
		print('YES')
	else:
		new = 0
		ans = 0
		for i in s:
			new ^= i
			if new == xor:
				new = 0
				ans += 1
		print(['NO', 'YES'][ans > 1])
import sys
sys.setrecursionlimit(2300)

def q3partition():

	def partition():
		if tol % 2:
			return 0
		up = tol
		rec = [[False] * (up + 2) for _ in range(n + 1)]
		rec[0][0] = True
		for i in range(1, n + 1):
			v = l[i - 1]
			for j in range(up + 1):
				if rec[i - 1][j]:
					if v + j <= up:
						rec[i][j + v] = True
					rec[i][j] = True
		return rec[n][tol // 2]

	def ints(x):
		nonlocal tol
		nonlocal gcf
		x = int(x)
		tol += x
		gcf = math.gcd(gcf, x) if gcf != float('inf') else x
		return x
	n = int(input())
	tol = 0
	gcf = float('inf')
	l = list(map(ints, input().split()))
	if partition():
		pos = 1
		for i in l:
			if i // gcf % 2:
				print(1)
				print(pos)
				return
			pos += 1
	else:
		print(0)

def main():
	q3partition()

def permu(n, r):
	return math.factorial(n) // math.factorial(n - r)

def comb(n, r):
	return math.factorial(n) // math.factorial(r) * math.factorial(n - r)

def calc():
	n = int(input())
	ans = permu(n, n)
	for i in range(1, n + 1):
		ans -= comb(n, i)
	print(ans)

def order():
	for _ in range(int(input())):
		n = int(input())
		odd = []
		even = []
		for i in input().split():
			i = int(i)
			if i % 2:
				odd.append(i)
			else:
				even.append(i)
		print(*odd + even)
order()


import sys
import math

def ans(n):
	if n < 10:
		print(n)
		return
	c = 0
	while n > 0:
		c = c + n % 10
		n = n // 10
	ans(c)
for _ in range(int(input())):
	n = int(input())
	x = [int(n) for n in input().split()]
	even = []
	for i in x:
		if i % 2 == 0:
			even.append(i)
		else:
			print(i, end=' ')
	print(*even)


n_inputs = int(input())
(odd, even) = ([], [])
for input_n in range(n_inputs):
	n_members = int(input())
	heights = [int(mh) for mh in input().split()]
	(odd, even) = ([], [])
	for h in heights:
		if h % 2:
			odd.append(h)
			continue
		even.append(h)
	print(' '.join((str(i) for i in odd + even)))


for _ in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	a0 = []
	a1 = []
	for i in range(n):
		if m[i] % 2 == 1:
			a1.append(m[i])
		else:
			a0.append(m[i])
	print(*a1, end=' ')
	print(*a0)


import sys
import math

def solve(n, heights):
	evens = []
	odds = []
	for i in range(n):
		if heights[i] % 2 == 0:
			evens.append(heights[i])
		else:
			odds.append(heights[i])
	ans = evens + odds
	for h in ans:
		print(h, end=' ')
	print()
t = int(input())
for i in range(t):
	n = int(input())
	heights = [int(x) for x in input().split()]
	solve(n, heights)


def solve(array, n):
	l = 0
	r = n - 1
	k = 0
	while l < r:
		while array[l] % 2 != 0 and l < r:
			l += 1
			k += 1
		while array[r] % 2 == 0 and l < r:
			r -= 1
		if l < r:
			(array[l], array[r]) = (array[r], array[l])
	odd = array[:k]
	even = array[k:]
	odd.extend(even)
	return odd
t = int(input())
for i in range(t):
	n = int(input())
	array = [int(x) for x in input().split()]
	ans = solve(array, n)
	for j in ans:
		print(j, end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	c = []
	for i in range(len(a)):
		if a[i] % 2 == 0:
			b.append(str(a[i]))
		else:
			c.append(str(a[i]))
	b = b + c
	print(' '.join(b))


for __ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	ans = []
	for elem in ar:
		if elem % 2 == 0:
			ans.append(elem)
	for elem in ar:
		if elem % 2 == 1:
			ans.append(elem)
	print(*ans)


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


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


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


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


import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
	_ = sys.stdin.readline()
	numbers = [int(item) for item in sys.stdin.readline().strip().split()]
	print(' '.join([str(item) for item in sorted(numbers, key=lambda x: x % 2)]))


tc = int(input())
for i in range(tc):
	x = int(input())
	y = list(map(int, input().split()))
	list1 = ''
	list2 = ''
	for i in y:
		if i % 2 == 0:
			list1 += str(i) + ' '
		else:
			list2 += str(i) + ' '
	print(list2 + list1)


import sys
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = [int(x) for x in input().split()]
		odd = []
		even = []
		for a in A:
			if a % 2 == 1:
				odd.append(a)
			else:
				even.append(a)
		ans = odd + even
		print(*ans)
main()


for _ in [*open(0)][2::2]:
	arr = list(map(int, _.split()))
	even = ''
	odd = ''
	for i in arr:
		if i % 2:
			odd += str(i) + ' '
		else:
			even += str(i) + ' '
	print(even + odd)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	(res1, res2) = ([], [])
	for i in range(n):
		if a[i] % 2 == 0:
			res1.append(a[i])
		else:
			res2.append(a[i])
	res = res1 + res2
	print(*res)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = int(1000000000.0) + 7

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k % mod
	t = power(k, n // 2)
	return t * t % mod

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		a1 = []
		a2 = []
		for i in a:
			if i % 2:
				a1.append(i)
			else:
				a2.append(i)
		for i in a1:
			print(i, end=' ')
		for i in a2:
			print(i, end=' ')
		print('')
	return
main()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	e = []
	o = []
	for j in a:
		if j % 2 == 0:
			e.append(j)
		else:
			o.append(j)
	x = e + o
	for k in x:
		print(k, end=' ')
	print()


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


t = int(input())
for i in range(t):
	n = int(input())
	ls = list(map(int, input().split()))
	(ls1, ls2) = ([], [])
	for j in range(n):
		if ls[j] % 2 == 0:
			ls2.append(ls[j])
		else:
			ls1.append(ls[j])
	(a, b) = (len(ls1), len(ls2))
	if a >= b:
		for k in range(a):
			if k == n - 1:
				print(ls[k])
			else:
				print(ls1[k], end=' ')
		for k in range(b):
			if k == n - 1:
				print(ls2[k])
			else:
				print(ls2[k], end=' ')
	else:
		for k in range(b):
			if k == n - 1:
				print(ls2[k])
			else:
				print(ls2[k], end=' ')
		for k in range(a):
			if k == n - 1:
				print(ls[k])
			else:
				print(ls1[k], end=' ')


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


from sys import stdin, stdout
input = stdin.readline

def getInput():
	return sys.stdin.readline().strip()

def getInt():
	return int(getInput())

def getInts():
	return map(int, getInput().split())

def getArray():
	return list(getInts())
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	even = []
	odd = []
	for i in li:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	odd.extend(even)
	print(*odd)


def changeStudent(a):
	(b, c) = ([], [])
	for i in a:
		if i % 2 == 0:
			c.append(i)
		else:
			b.append(i)
	for i in c:
		b.append(i)
	return b
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = changeStudent(a)
	for i in b:
		print(i, end=' ')
	print(end='\n')


from sys import stdin as inp
for _ in range(int(inp.readline())):
	n = int(inp.readline())
	deck = list(map(int, inp.readline().split()))
	ans = []
	for i in deck:
		if i % 2 == 0:
			ans.append(i)
		else:
			ans.insert(0, i)
	print(*ans)


def even(n):
	return n % 2 == 0
evens = []
odds = []
num_cases = int(input())
for _ in range(num_cases):
	num_nums = int(input())
	nums = input().split()
	for num in nums:
		if even(int(num)):
			evens.append(num)
		else:
			odds.append(num)
	print(' '.join(evens + odds))
	evens = []
	odds = []