Sorting is considered to be one of the most important skills to be learned in computer science and has it's applications in real product building.
The problem has arised to the team of PcCube.They need to sort the set of alphanumeric strings in such a way that the positions of alphabets and numbers remains unchanged. 

Input
First line of the input contains T , i.e. number of test cases.Then next T lines contains a string S.

Output
Output description.
Output the sorted form of S such that the positions of alphabets and numbers remains unchanged.

Constraints

1 ≤ T ≤ 100
1 ≤ N ≤ 1000000

Example
Input:
1
951f5gd3

Output:
135d5fg9

见题面

见题面