给定一个仅由数字 构成的字符串 。一次操作可按如下方式进行: 从 中选择既不是最左端字符也不为 的某一字符; 将该字符的数值减少 ; 随后把它与左侧相邻字符交换位置。 例如,字符串 经过一次操作可以变成 或 。 你可以不限次数地执行上述操作。请计算能够得到的字典序最大的字符串,并输出该字符串。
输入描述:
第一行输入一个整数 ,表示测试用例数量。此后 行,每行输入一个不含前导零的数字字符串 ,满足 。保证所有测试用例的 之和不超过 。


输出描述:
对于每个测试用例,在一行上输出通过任意次数操作后能够得到的字典序最大的字符串。
示例1

输入

6
19
1709
11555
51476
9876543210
5891917899

输出

81
6710
33311
55431
9876543210
7875567711

说明

\hspace{15pt}\texttt{ 为例:
\hspace{23pt}\bullet\, \texttt{ \rightarrow \texttt{
\hspace{23pt}\bullet\, \texttt{ \rightarrow \texttt{,得到答案 \texttt{

\hspace{15pt}再以 \texttt{ 为例,可按如下序列操作:
\hspace{23pt}\bullet\, \texttt{ \rightarrow \texttt{
\hspace{23pt}\bullet\, \texttt{ \rightarrow \texttt{
\hspace{23pt}\bullet\, \texttt{ \rightarrow \texttt{,最终得到答案 \texttt{
加载中...