Make It Big!

You are given a number N (10 ≤ N ≤ 2×109).
You have to perform exactly two swap operation. You can choose any two unequal position of this number and swap digit of this two position.

Like, for number 451 you can choose position 1 and 2 then swap this after swapping number will 541 again you can choose position 2 and 3 and swap after swapping number become 514.

What is the largest number you can get after this two operation?

Input

Input start with a number t (1 ≤ t ≤ 103 ) denoting test case.
The next line of each case contains only integer N (10 ≤ N ≤ 2×109).

Output

Print the largest number you can get after swapping exactly two time in one line

Sample

Input	Output
2 4213 154	4321 541