交换到最大

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine(); // 处理换行符
        
        while (n-- > 0) {
            // 读取字符串并转为整数数组
            char[] chars = in.nextLine().toCharArray();
            int[] s = new int[chars.length];
            for (int i = 0; i < chars.length; i++) {
                s[i] = chars[i] - '0';
            }

            boolean flag = true;
            // 循环执行操作直到无法继续
            while (flag) {
                flag = false;
                // 从右向左执行一***作
                for (int i = s.length - 1; i > 0; i--) {
                    // 满足差值≥2时交换并减1
                    if (s[i] - s[i - 1] >= 2) {
                        int tmp = s[i];
                        s[i] = s[i - 1];
                        s[i - 1] = tmp - 1;
                    }
                }
                // 检查是否还能操作
                for (int i = s.length - 1; i > 0; i--) {
                    if (s[i] - s[i - 1] >= 2) {
                        flag = true;
                        break;
                    }
                }
            }
            
            // 输出结果
            for (int i : s) {
                System.out.print(i);
            }
            System.out.println();
        }
    }
}