输入n和n个各不相等的整数(1<n<100),将这些整数从小到大进行排序,要求奇数在前,偶数在后.
第一行表示测试总数t.然后是t组测试数据,每组包含n,以及随后的n个整数.

Sample Input

3
5 1 2 3 4 5
3 12 4 5
6 2 4 6 8 0 1

Sample Output

1 3 5 2 4
5 4 12
1 0 2 4 6 8