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.
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".
1 <= t <= 1e41 <= |s| <= 2 * 1e5- It's guaranteed that the sum of lengths of
sover all test cases does not exceed2 * 1e5.
input:
output: