#P1730C. Minimum Notation
-
ID: 808
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 4
Uploaded By:
Hydro
Tags> Minimum Notation
Description
You have a string consisting of digits from to inclusive. You can perform the following operation any (possibly zero) number of times:
- You can choose a position and delete a digit on the -th position. Then insert the digit 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 is lexicographically smaller than a string of the same length if and only if the following holds:
- in the first position where and differ, the string has a smaller digit than the corresponding digit in .
The first line contains a single integer () — the number of test cases. Then the test cases follow.
Each test case consists of a single line that contains one string () — the string consisting of digits. Please note that is just a string consisting of digits, so leading zeros are allowed.
It is guaranteed that the sum of lengths of over all test cases does not exceed .
Print a single string — the minimum string that is possible to obtain.
Input
The first line contains a single integer () — the number of test cases. Then the test cases follow.
Each test case consists of a single line that contains one string () — the string consisting of digits. Please note that is just a string consisting of digits, so leading zeros are allowed.
It is guaranteed that the sum of lengths of over all test cases does not exceed .
Output
Print a single string — the minimum string that is possible to obtain.
Note
In the first test case:
- Delete and insert at the end of the notation. The resulting notation is .
- Delete and insert in the -rd position of the notation. The resulting notation is .
Nothing needs to be done in the second and third test cases.