题目描述

刘桑穿越到了$2077$年成为了一名边缘行者，为了获得最强的义肢，刘桑需要攻破一个密码锁。密码锁是一个由$0$到$9$组成的字符串$s$。他可以执行以下操作任何次（可能是$0$次）去改变这个字符串。

选择一个位置$i$，删除第$i$个位置上的数字$d$，然后在任何位置（开始，结尾，或字符串中任意位置）上插入数字$min(d+1,9)$。

只有把字符串$s$转变成字典序最小的字符串才可以解锁，因为刘桑在与警卫局周旋，解锁这个任务就交给了你，请帮助刘桑完成解锁。

输入格式

第一行包含一个整数$t$，表示测试案例的数量。

接下来$t$行，每行一个字符串$s，(1<|s|<1e5)$。

保证所有测试案例中$s$的长度之和不超过$1e5$。

输出格式

一个处理后的字符串，且字典序最小。

样例

样例输入1

4
04829
9
01
314752277691991

样例输出1

02599
9
01
111334567888999

样例解释

在第一个测试案例中：

​ 删除$8$，在串末尾插入$9$，由此产生的串是$04299$。

​ 删除$4$，在串的第$3$个位置插入$5$，结果是$02599$。

在第二个和第三个测试案例中不需要操作。