Friendship String

John and Mary, good friends, play a game to see how strong their friendship is. John gives Mary a tricky puzzle to solve. Here's how it goes: Given a string s consisting of digits from 0 to 9 inclusive, You can choose a position i and delete a digit d on the ith position. Then Insert the digit min (d+1, 9) in any position (at the beginning, at the end or in between any two adjacent digits. What is the lexicographically smallest string you can get by performing these operations? A string 'a' is lexicographically smaller than a string 'b' of the same length of and only if the following holds: In the first position where a and b differ, the string 'a' has a smaller digit than the corresponding digit. Help Mary prove her friendship by solving the puzzle. Input Format The first line contains a single integer t -- the number of test cases. Then the test cases follow. Each test case consists of a single line that contains one string s. the string consisting of digits. Please note that s is just a string consisting of digits, so leading zeros are allowed. Output Format Print a single string the lexicographically smallest string that is possible to obtain.

Constraints

• 1 ≤ t ≤ 1e4
• 1 ≤ |s| ≤ 2 * 1e5
• It's guaranteed that the sum of lengths of s

Example 1

Input:

s = "415863388791991"

Output:

"111334567888999"

Explanation: By performing the operations as per the rules, the lexicographically smallest string that can be obtained is "111334567888999".