By now, you should have realized that Rubrik values your work. But you cannot always perform all your tasks, the hard way. Instead you decide to work smartly. But you soon have a self realization that you lack skills for it, so you hypothesize a task to get an estimate on your smartness.
You took a huge number, consisting of n digits. The number may contain leading zeros. You choose to perform the following operation any number of times (possibly zero): You can swap two adjacent digits, if those digits have different parity. Two digits possess different parity, if they have different remainders when divided by 2.
You have to find the minimum number you can obtain. The resultant may contain leading zeros.
Input Format
The first line contains an integer t the number of test cases. Each line of each test case contains a single integer a, of n digits.
Output Format
For each test case, print a line with the minimum integer you can obtain.
Example 1:
Input: a = "4321"
Output: 3142
Explanation:By swapping the first and second digits, the number becomes 3421. Then, by swapping the second and third digits, it becomes 3241. Finally, by swapping the third and fourth digits, it becomes 3142, which is the minimum number that can be obtained.
- 1 ≤
t≤ 104 - 1 ≤
n≤ 105 - The sum of
nacross all test cases ≤ 1015
input:
output: