Description:
You have a string $$$s$$$ consisting of digits from $$$0$$$ to $$$9$$$ inclusive. You can perform the following operation any (possibly zero) number of times:
- You can choose a position $$$i$$$ and delete a digit $$$d$$$ on the $$$i$$$-th position. Then insert the digit $$$\min{(d + 1, 9)}$$$ on 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 if 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 in $$$b$$$.
Input Format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then the test cases follow.
Each test case consists of a single line that contains one string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$) — the string consisting of digits. Please note that $$$s$$$ is just a string consisting of digits, so leading zeros are allowed.
It is guaranteed that the sum of lengths of $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
Output Format:
Print a single string — the minimum string that is possible to obtain.
Note:
In the first test case:
- Delete $$$8$$$ and insert $$$9$$$ at the end of the notation. The resulting notation is $$$04299$$$.
- Delete $$$4$$$ and insert $$$5$$$ in the $$$3$$$-rd position of the notation. The resulting notation is $$$02599$$$.
Nothing needs to be done in the second and third test cases.