URI Online Judge | 3103

Lucky Number

By Ygor Ribeiro, IFSULDEMINAS BR Brazil

Timelimit: 1

Neymar is a very smart boy and loves numbers, he has several little pieces with digits from 0 to 9. He lives assembling many different numbers with these figures, for example: If Neymar goes to his box where his pieces are kept and picks them up 5, being {5, 8, 6, 8, 0}, it can form the numbers 56808, 68805, 88065 among others. It is important to emphasize that the number 08685 is not valid, nor any other number that starts with leading zeros.

One day Neymar formed a number that he particularly liked a lot and said that it would be his lucky number, so he left the number formed on his bed and said he would get his cell phone to take a picture of that number so he would never forget it.

When he was returning to his room, he slipped and fell on the bed, totally messing up his number. Neymar was very sad, as he had not memorized what the number was, but he knew a clue: His lucky number was the smallest possible number formed by the figures that were initially messed up.

As the boy is very nervous and sad, he is not able to think straight and form his lucky number again, can you help him?

You will be given a random number that formed after the mess of the digits and you must inform Neymar what your lucky number is.

Input

The input contains an integer T (1 <= T <= 100) that represents the number of test cases. Each of the following T lines contains an integer N (1 <= N <= 10 ^ 100).

Output

The exit should contain Neymar's lucky number followed by a line break.

Input Sample Output Sample

3

548451

95480009694

51809580050

144558

40004558999

10000555889