D. 数字串最大化

每个测试用例时间限制： $2$ 秒 每个测试用例内存限制： $256$ 兆字节

给你一个由数字 $0$ 到 $9$ 组成的字符串 $s$ 。在一次操作中，你可以选取这个字符串中的任意一个数字（不能是 $0$ ，也不能是最左侧的数字），将其减 $1$ ，然后把它和它左边的那个数字交换。

例如，通过一次操作，可以从字符串 $1023$ 得到 $1103$ 或 $1022$ 。

请你求出执行任意次操作后，字典序最大的字符串。

输入

第一行输入一个整数 $t$ （ $1 \le t \le 10^4$ ）—— 表示测试用例的数量。

每个测试用例单独占一行，包含一个数字字符串 $s$ （ $1 \le |s| \le 2 \cdot 10^5$ ），其中 $|s|$ 表示字符串 $s$ 的长度。字符串不含前导零。

保证所有测试用例的字符串长度之和不超过 $2 \cdot 10^5$ 。

对于每个测试用例，在单独一行中输出答案。

在第一个样例中，下面的操作序列是可行的： $19 \to 81$ 。

在第二个样例中，下面的操作序列是可行的： $1709 \to 1780 \to 6180 \to 6710$ 。

在第四个样例中，下面的操作序列是可行的：$51476 \to 53176 \to 53616 \to 53651 \to 55351 \to 55431$。