CF1251C Minimize The Integer

给定一个由 $n$ 位数字组成的巨大整数 $a$（$n$ 的取值范围为 $1$ 到 $3 \cdot 10^5$，包含端点）。该整数可能包含前导零。 你可以交换相邻位置上的两个数字，当且仅当这两个数字的奇偶性不同（即它们除以 $2$ 的余数不同）。 例如，如果 $a = 032867235$，你可以通过一次操作得到以下整数： - 如果交换第 $1$ 位和第 $2$ 位，可以得到 $302867235$； - 如果交换第 $2$ 位和第 $3$ 位，可以得到 $023867235$； - 如果交换第 $5$ 位和第 $6$ 位，可以得到 $032876235$； - 如果交换第 $6$ 位和第 $7$ 位，可以得到 $032862735$； - 如果交换第 $7$ 位和第 $8$ 位，可以得到 $032867325$。 注意，你不能交换第 $2$ 位和第 $4$ 位，因为它们不是相邻的。同样，你也不能交换第 $3$ 位和第 $4$ 位，因为这两个数字的奇偶性相同。 你可以进行任意次数（也可以为零）这样的操作。 请你求出能够得到的最小整数。 注意，结果整数也可能包含前导零。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的一行包含一个整数 $a$，其长度 $n$ 满足 $1 \le n \le 3 \cdot 10^5$。 保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

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

在第一个测试用例中，你可以进行如下操作（被交换的数字用下划线和加粗表示）：$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$。 由 ChatGPT 4.1 翻译