CF1251C.Minimize The Integer

You are given a huge integer $a$ consisting of $n$ digits ($n$ is between $1$ and $3 \cdot 10^5$, inclusive). It may contain leading zeros.

You can swap two digits on adjacent (neighboring) positions if the swapping digits are of different parity (that is, they have different remainders when divided by $2$).

For example, if $a = 032867235$ you can get the following integers in a single operation:

• $302867235$ if you swap the first and the second digits;
• $023867235$ if you swap the second and the third digits;
• $032876235$ if you swap the fifth and the sixth digits;
• $032862735$ if you swap the sixth and the seventh digits;
• $032867325$ if you swap the seventh and the eighth digits.

Note, that you can't swap digits on positions $2$ and $4$ because the positions are not adjacent. Also, you can't swap digits on positions $3$ and $4$ because the digits have the same parity.

You can perform any number (possibly, zero) of such operations.

Find the minimum integer you can obtain.

Note that the resulting integer also may contain leading zeros.

给你一个由 $n$ 位数字组成的极大整数 $a$（$n$ 的取值范围为 $1$ 到 $3 \cdot 10^5$，含端点）。该整数可能包含前导零。

你可以在相邻（即位置相邻）的两个位置上交换数字，当且仅当这两个数字的奇偶性不同（即它们除以 $2$ 的余数不同）。

例如，若 $a = 032867235$，则一次操作可得到以下整数：

• $302867235$：交换第 $1$ 位与第 $2$ 位；
• $023867235$：交换第 $2$ 位与第 $3$ 位；
• $032876235$：交换第 $5$ 位与第 $6$ 位；
• $032862735$：交换第 $6$ 位与第 $7$ 位；
• $032867325$：交换第 $7$ 位与第 $8$ 位。

注意：你不能交换位置 $2$ 和 $4$ 上的数字，因为这两个位置不相邻；你也不能交换位置 $3$ 和 $4$ 上的数字，因为这两个数字奇偶性相同。

你可以执行任意次数（包括零次）这样的操作。

请找出你能得到的最小整数。

注意：结果整数也可能包含前导零。

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input.

The only line of each test case contains the integer $a$, its length $n$ is between $1$ and $3 \cdot 10^5$, inclusive.

It is guaranteed that the sum of all values $n$ does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 输入中测试用例的数量。

每个测试用例仅有一行，包含整数 $a$，其长度 $n$ 在 $1$ 到 $3 \cdot 10^5$ 之间（含端点）。

保证所有 $n$ 的总和不超过 $3 \cdot 10^5$。

For each test case print line — the minimum integer you can obtain.

对于每个测试用例，输出一行——你能得到的最小整数。

In the first test case, you can perform the following sequence of operations (the pair of swapped digits is highlighted): $0 \underline{\textbf{70}} 9 \rightarrow 0079$.

In the second test case, the initial integer is optimal.

In the third test case you can perform the following sequence of operations: $246 \underline{\textbf{43}} 2 \rightarrow 24 \underline{\textbf{63}}42 \rightarrow 2 \underline{\textbf{43}} 642 \rightarrow 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$。