#P0019. 交换到最大

交换到最大

题目描述

给你一个由 00 至 99 的数字组成的字符串 ss 。在一次运算中,您可以选取该字符串中除 00 或最左边数字之外的任意数字,将其减少 11 ,然后将其与左边的数字对调。

例如,从字符串 10231023 中进行一次运算,可以得到 11031103 或 10221022 。

找出任意多次运算后所能得到的字典序最大的字符串。

输入格式

输入的第一行是一个整数 tt ( 1≤t≤1041 \le t \le 10^4 ) - 测试用例的数量。

每个测试用例由一行数字字符串 ss ( 1≤∣s∣≤2⋅1051 \le |s| \le 2\cdot 10^5 ) 组成,其中 ∣s∣|s| 表示 ss 的长度。字符串不包含前导零。

保证所有测试用例的 ∣s∣|s| 之和不超过 2⋅1052\cdot 10^5 。

输出格式

对于每个测试用例,在单独一行中打印其对应的答案。

样例 #1

样例输入 #1

6
19
1709
11555
51476
9876543210
5891917899

样例输出 #1

81
6710
33311
55431
9876543210
7875567711

样例解释

在第一个样例中,以下操作顺序是合适的: 19→8119 \rightarrow 81 .

在第二个样例中,适合使用以下操作序列: $1709 \rightarrow 1780 \rightarrow 6180 \rightarrow 6710$ .

在第四个样例中,以下操作序列是合适的: $51476 \rightarrow 53176 \rightarrow 53616 \rightarrow 53651 \rightarrow 55351 \rightarrow 55431$ .