题目描述

现有 n 个数排成一行，如果两个相邻的数 u 和 v 的平均数为整数，则认为它们是 “ 上镜 ” 的。

如何将这些数重新排列，使得 “ 上镜 ” 数对的数量最大？

输入格式

第一行包含一个整数 t（1≤t≤500）,即测试用例数。

每个测试用例的第一行包含一个整数 n （2≤n≤2000）表示有 n 个数。

每个测试用例的第二行包含 n 个整数 ， 每个整数不超过 $2\cdot10^5$

输出格式

对于每个测试用例，在一行输出 n 个整数，表示调整后的数列。如果有多个情况，则输出其中任何一个。

样例

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

1 1 2 
1 1 1 
13 9 13 15 3 9 16 10 
9 18