给你一个巨大的整数 $$$a$$$,由 $$$n$$$ 数字组成($$$n$$$ 介于 $$$1$$$ 和 $$$3 \cdot 10^5$$$ 之间,包括在内)。它可能包含前导零。
如果交换的数字具有不同的奇偶校验(即除以 $$$2$$$ 时有不同的余数),则可以交换相邻(相邻)位置上的两个数字。
例如,如果 $$$a = 032867235$$$ 您可以在一次操作中获得以下整数:
- $$$302867235$$$ 如果你交换第一个和第二个数字;
- $$$023867235$$$ 如果交换第二个和第三个数字;
- $$$032876235$$$ 如果你交换第五位和第六位数字;
- $$$032862735$$$ 如果你交换第六位和第七位数字;
- $$$032867325$$$ 如果交换第七位和第八位数字。
请注意,您不能交换位置 $$$2$$$ 和 $$$4$$$ 上的数字,因为这些位置不相邻。另外,您不能交换 $$$3$$$ 和 $$$4$$$ 位置上的数字,因为这些数字具有相同的奇偶性。
您可以执行任意数量(可能为零)的此类操作。
找出你能得到的最小整数。
请注意,生成的整数也可能包含前导零。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。
每个测试用例的唯一行包含整数 $$$a$$$,其长度 $$$n$$$ 介于 $$$1$$$ 和 $$$3 \cdot 10^5$$$(含)之间。
保证所有值 $$$n$$$ 的总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例打印行 - 您可以获得的最小整数。
示例
输入 #1
3 0709 1337 246432
输出 #1
0079 1337 234642
注意
在第一个测试用例中,您可以执行以下操作序列(一对交换的数字突出显示):$$$0 \underline{\textbf{70}} 9 \rightarrow 0079$$$。
在第二个测试用例中,初始整数是最佳的。
在第三个测试用例中,您可以执行以下操作序列:$$$246 \underline{\textbf{43}} 2 \rightarrow 24 \underline{\textbf{63}}42 \rightarrow 2 \underline{\textbf{43}} 642 \rightarrow 234642$$$。