Dr. Ramanujam is a great mathematician and working at FAU Miami as a professor. During the internal assessment professor Ramanujam has given a problem to his students and ask then to solve the problem within an hour. The problem statement is as follows:

Suppose there is a number ’a’ which consist of n digits and may have the leading zeros. Now the role of students to swap two adjacent digits with following conditions.

Swapping will take place if both digits have different remainders when divided by 2.

Students can perform any number of similar swapping and share the value of smallest integer with Prof. Ramanujam. Now your role is to find the value of smallest integer generated after similar operations.

302867235 if you swap the first and the second digits;

023867235 if you swap the second and the third digits;

032876235 if you swap the fifth and the sixth digits;

032862735 if you swap the sixth and the seventh digits;

032867325 if you swap the seventh and the eighth digits.

Input

The first line contains one integer t (1≤t≤104) — Number of test cases.

The only line of each test case contains the integer a, its length n is between 1 and 3⋅105, inclusive.

It is guaranteed that the sum of all values n does not exceed 3⋅105.

Input

The first line contains one integer t (1≤t≤104) — Number of test cases.

The only line of each test case contains the integer a, its length n is between 1 and 3⋅105, inclusive.

It is guaranteed that the sum of all values n does not exceed 3⋅105.

Output:

Print the minimum integer got after the operations.

Print the minimum integer got after the operations.