Lexicographically Smallest String

Given a string S that consists of lowercase letters, uppercase letters, and digits, you are allowed to perform the following operation any number of times:

• You can swap any two adjacent characters if exactly one of them is a digit and the other is a letter.

Your task is to determine the lexicographically smallest string that can be obtained by applying the operation arbitrarily many times.

Note: The final answer is actually achieved by sorting the letters among themselves and the digits among themselves separately, and then concatenating the sorted letters with the sorted digits.

Example:

Input: a1b2c3
Output: abc123

inputFormat

The first line of input contains an integer T, representing the number of test cases.

Each of the following T lines contains a non-empty string S consisting of lowercase letters, uppercase letters, and digits.

You should read input from standard input (stdin).

outputFormat

For each test case, output the lexicographically smallest string that can be obtained, each on a new line.

Output to standard output (stdout).

## sample

3
a1b2c3
1a2b3c
a2a1a

abc123
abc123
aaa12

</p>