题目描述

给你一个大整数$a$，它由$n$位数字组成（$n$在$1$到$3 \times 10 ^ 5$之间）。它有可能会包含前导零。

你可以交换相邻位置的两个数字，如果这两个数字奇偶性不同（换言之，它们被二除的余数不同）。

举例来说：如果$a = 032867235$，你可以通过一次操作得到下面的整数：

• $302867235$ 如果你交换第一个和第二个数字
• $023867235$ 如果你交换第二个和第三个数字
• $032876235$ 如果你交换第五个和第六个数字
• $032862735$ 如果你交换第六个和第七个数字
• $032867325$ 如果你交换第七个和第八个数字

注意：你不能更换第二个和第四个数字，因为他们不相邻。你也不能更换第三个和第四个数字因为他们的奇偶性相同。

你可以做任意次操作（当然也可能不做）。

请你找到通过这种操作可以得到的最小整数。

注意答案也可以有前导零。

输入格式

第一行一个正整数 $t$ ( $1 \le t \le 10^4$ )，表示数据组数。

接下来 $t$ 行，每行一个长度为n的仅包含数字的字符串。

保证所有字符串的长度之和不超过$3 \cdot 10^5$ 。

输出格式

$t$ 行，每行一个字符串，表示可能得到的最小整数。

样例输入 #1

3
0709
1337
246432

样例输出 #1

0079
1337
234642