题目描述

有 $n$ 个玩具按一列排成，第 $i$ 个玩具的编号（或值）为 $a_i$。你可以使用一根坏掉的魔杖来交换玩具：魔杖 只能 交换两件玩具，当且仅当它们的整数 奇偶性不同（一个为偶数，另一个为奇数）。也就是说，允许交换位置 $(i,j)$ 当且仅当 $a_i \bmod 2 \ne a_j \bmod 2$。

在任意次数的允许交换之后，问你能够得到的按字典序（即从左到右第一个不同位置上的值较小者更小）最小的序列是什么？输出该序列。

输入格式

第一行包含一个整数 $t$，表示测试用例数量（$1 \le t \le 10^4$）。

之后是 $t$ 个测试用例，每个测试用例两行：

• 第一行包含整数 $n$，表示玩具个数（$1 \le n \le 2\cdot10^5$）。
• 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^9$）。

附加约束：所有测试用例中 $\sum n \le 2\cdot10^5$。

输出格式

对每个测试用例，输出一行，包含 $n$ 个整数——使用魔杖后可以得到的字典序最小的序列（元素之间用空格分隔）。

样例输入

7
4
2 3 1 4
5
3 2 1 3 4
4
3 7 5 1
2
1000000000 2
3
1 3 5
5
2 5 3 1 7
4
2 4 8 6

样例输出

1 2 3 4
1 2 3 3 4
3 7 5 1
1000000000 2
1 3 5
1 2 3 5 7
2 4 8 6

说明

样例解释

在第一个测试用例中，我们可以交换位置 $(1, 3)$ ，然后交换位置 $(2, 3)$ 。

在第二个测试用例中，我们可以交换位置 $(1, 2)$ 、 $(1, 3)$ ，然后是 $(2, 3)$ 。

在第三个和第四个测试用例中，我们无法交换任何位置，因为所有玩具整数都具有相同的奇偶校验。