排序

题号：NC259242
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给出一个长度为 $n$ 的只包含数字 $0\sim9$ 的字符串 $S$ ，下标从 $1$ 开始。如果两个相邻的数的差的绝对值等于 $1$ ，那么这两个数执行互换操作，特别地，数字 $0$ 和 $9$ 可以互换。

更正式地说，任意下标 $i\in[1,n-1]$ ，如果 $abs(S[i]-S[i+1])=1$ 或 $abs(S[i]-S[i+1])=9$ ，那么可以 $swap(S[i],S[i+1])$ 。

问：执行任意次互换操作（也可以不执行），使得字符串字典序最小，输出能得到的字典序最小的字符串。

第一行包含一个整数 $T\ (1\le T\le10^5)$ ，表示样例个数。

接下来 $T$ 行，每行包含一个字符串 $S$ 。

数据保证 $1\le length(S)\le10^7,1\le\sum length(S)\le10^7$ 。

输出包含  行，每行包含一个字符串，表示通过任意次操作得到的最小字典序的字符串。

示例1

复制

复制

012
1223
896745231