Young Matt and Jeff loved playing with numbers. One fine day, when Matt's little brother Paul, was at his math lesson with plastic number toys i.e. plastic toys in shape of digits 0 to 9, Matt and Jeff decided to play a game.
Paul had left the plastic numbers arranged to form a number N.
The rules of the game were as follows:

• The first player has to rearrange the digits to form a larger number than the current number, after that the game will be played turn-wise.
• After the first turn, each player has to rearrange the digits so that it is smaller than the current number in that turn and greater than the original number N.
• The player loses if he cannot arrange a number.

What number should the first player form, so that he always wins?

Input

An integer T (1 = T = 100) denoting number of test cases followed by T lines each containing an integer N, the number Paul has formed. The number of digit in N is D(1 = D = 100000).

Output

For each test case, output a number which first player should form so that he wins, in a separate line.
If there is no winning strategy for first player, then output -1.

Example

Input: 3 17 81 123 Output: 71 -1 132