FastPrepFastPrep
Problem Brief

Doing Smart Work

OA

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.

1Example 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.

Constraints

Limits and guarantees your solution can rely on.

  • 1 ≤ t ≤ 104
  • 1 ≤ n ≤ 105
  • The sum of n across all test cases ≤ 1015
    • public int getMinimumNumber(String a) {
  // write your code here
}
    Input

    a

    "4321"

    Output

    3142

    Sign in to submit your solution.