Alia the beginner mathematician. She is now learning the addition operation. The teacher has written down the sum of multiple numbers. Pupils should calculate the sum. Still, that isn't enough for Alia. But Alia is just a beginner, so she can calculate a sum only if the numbers follow in non-decreasing order. For example, she can't calculate sum 1+3+2+1 but she can calculate sums 1+1+2 and 3+3.

You've got the question that was written on the board. Rearrange the question in such a way that Alia can calculate the sum.

Input

The first line contains T(<=10): number of test cases.

Each test case contains a non-empty string S: the sum Alia needs to count. String s contains no spaces. 

It only contains digits and characters "+". Besides, string S is a correct sum of numbers.

The string S has atmost n(<=1000) numbers(all in integer range) apart from the '+'.

Output

For each of the T test cases print a line having the new question that Alia can calculate.

Example

Sample Input:

2
1+1+3+1+3
6

Sample Output:

1+1+1+3+3
6