远端评测题 1000ms 256MiB

Minimum Notation

本题没有可用的提交语言。

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

You have a string ss consisting of digits from 00 to 99 inclusive. You can perform the following operation any (possibly zero) number of times:

  • You can choose a position ii and delete a digit dd on the ii-th position. Then insert the digit min(d+1,9)\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 aa is lexicographically smaller than a string bb of the same length if and only if the following holds:

  • in the first position where aa and bb differ, the string aa has a smaller digit than the corresponding digit in bb.

The first line contains a single integer tt (1t1041 \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 ss (1s21051 \le |s| \le 2 \cdot 10^5) — the string consisting of digits. Please note that ss is just a string consisting of digits, so leading zeros are allowed.

It is guaranteed that the sum of lengths of ss over all test cases does not exceed 21052 \cdot 10^5.

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

Input

The first line contains a single integer tt (1t1041 \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 ss (1s21051 \le |s| \le 2 \cdot 10^5) — the string consisting of digits. Please note that ss is just a string consisting of digits, so leading zeros are allowed.

It is guaranteed that the sum of lengths of ss over all test cases does not exceed 21052 \cdot 10^5.

Output

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

Samples

样例输入 1

4
04829
9
01
314752277691991

样例输出 1

02599
9
01
111334567888999

Note

In the first test case:

  • Delete 88 and insert 99 at the end of the notation. The resulting notation is 0429904299.
  • Delete 44 and insert 55 in the 33-rd position of the notation. The resulting notation is 0259902599.

Nothing needs to be done in the second and third test cases.

FJNU·ACM-22级新手村の第四场世纪大战

未参加
状态
已结束
规则
ACM/ICPC
题目
9
开始于
2022-10-29 9:30
结束于
2022-10-29 12:30
持续时间
3 小时
主持人
参赛人数
20