Minimum Notation

题意翻译

给定一个仅包含 $0$ 到 $9$ 这几个数字的字符串，你可以执行以下操作任意次： 选择字符串中的一个数字 $d$，将 $d$ 删除后，向字符串任意位置插入一个数字 $\min(d+1,9)$. 求能够得到的字典序最小的字符串。

题目描述

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 $ .

输入输出格式

输入格式

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 $ .

输出格式

Print a single string — the minimum string that is possible to obtain.

输入输出样例

输入样例 #1

4
04829
9
01
314752277691991

输出样例 #1

02599
9
01
111334567888999

说明

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.

**最小记号**

**题目大意：**
给定一个由数字0到9组成的字符串，你可以进行任意次以下操作：
- 选择字符串中的一个数字$d$，删除它，然后在字符串的任意位置插入一个数字$\min(d+1, 9)$。
目标是得到字典序最小的字符串。

**输入输出格式：**
- **输入格式：** 第一行包含一个整数$t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是$t$个测试用例，每个测试用例一行，包含一个由数字组成的字符串$s$（$1 \le |s| \le 2 \cdot 10^5$）。
- **输出格式：** 对于每个测试用例，输出一行，表示可能获得的最小字符串。

**输入输出样例：**
- **输入样例：**
```
4
04829
9
01
314752277691991
```
- **输出样例：**
```
02599
9
01
111334567888999
```**最小记号** **题目大意：** 给定一个由数字0到9组成的字符串，你可以进行任意次以下操作： - 选择字符串中的一个数字$d$，删除它，然后在字符串的任意位置插入一个数字$\min(d+1, 9)$。 目标是得到字典序最小的字符串。 **输入输出格式：** - **输入格式：** 第一行包含一个整数$t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是$t$个测试用例，每个测试用例一行，包含一个由数字组成的字符串$s$（$1 \le |s| \le 2 \cdot 10^5$）。 - **输出格式：** 对于每个测试用例，输出一行，表示可能获得的最小字符串。 **输入输出样例：** - **输入样例：** ``` 4 04829 9 01 314752277691991 ``` - **输出样例：** ``` 02599 9 01 111334567888999 ```