## 题目大意

给定一个正整数 x，要求找到一个大于等于 x 的最小整数 y，使得 y 的各位数字互不相同。我们把这种数位互不相同的数称为“好数”。

例如，输入 1233，输出 1234。输入 989，输出 1023。

## 核心思路 💡

最直接的暴力方法（逐一加一检查）容易超时。更高效的解法是构造法。我们的目标是让找到的答案 y 和 x 尽可能接近，这意味着 y 应该和 x 拥有尽可能长的相同前缀。

这个思路引导我们采用一种**“回溯修改”**的策略：

  1. 如果 x 本身就是好数，那它就是答案。
  2. 如果 x 不是好数，我们从左到右找到第一个重复的数字，这个位置就是问题的关键。
  3. 为了得到比 x 大的、且增幅最小的数字，我们必须修改这个重复位或它左边的某一位。显然，越靠右的修改，对数字大小的影响越小。
  4. 因此，我们从这个重复数字的位置开始，从右向左回溯，尝试将当前位的数字加一。并且，这个回溯过程本身还可以通过状态优化进一步提升效率，避免重复计算。
  5. 一旦我们成功替换了某一位的数字，这个新前缀就确定了。剩下的后缀部分，我们应该用当前还未被使用过的、最小的数字按升序依次填充。
  6. 如果回溯到最高位都找不到可行的替换方案，答案必然是一个位数+1的最小好数（例如1023）。

## 算法步骤 📝

下面是包含了状态优化的算法实现步骤：

  1. 检查自身：将输入数字 x 转为字符串 s。遍历 s，使用一个集合（Set）来检查是否存在重复数字。如果不存在，s 本身就是答案，程序结束。
  2. 定位错误点：在遍历过程中，记录下第一个重复数字的索引 first_dupe_idx。
  3. 回溯修改与状态优化：a. 初始化状态：在回溯开始前（即 j = first_dupe_idx 时），我们只创建一次前缀 s[0...j-1] 中使用过的数字集合 used。b. 开始回溯：然后开始一个循环，从 j 递减至 0。c. 查找替换：在每个 j，我们使用这个 used 集合来寻找一个 > s[j] 的可用替换数字 d。如果找到了，就进入下一步（构造后缀）。d. 高效更新状态：如果在当前 j 找不到可行的替换数字，我们就将 j 减一，并从 used 集合中移除s[j] 这个数字。这就完成了对 used 集合的高效更新，使其能准确反映新的、更短的前缀的状态，而无需重新扫描整个前缀来重建集合。
  4. 构造后缀：将 s 的前 j 位和找到的新数字 d 拼接成新的前缀 new_prefix。然后，从 0 到 9 开始遍历，依次找出还未被 new_prefix 使用过的最小数字，按顺序填充到后缀中，直到补齐 s 的原始长度。拼接好的 new_prefix 和后缀就是最终答案，打印并结束程序。
  5. 处理位数增加：如果回溯循环完整地执行完毕都没有找到任何可行的替换方案，则说明答案必须增加一位。此时，构造并打印出长度为 n+1 的最小好数即可（即 102...）。

## 代码实现 🏆

这是包含了状态优化的最终 Python 实现。

import sys

def solve(x_str):
    """
    最终优化版：通过高效的状态管理进行剪枝，避免重复计算。
    """
    n = len(x_str)

    # 步骤 1: 检查输入 x_str 本身是否为好数
    seen = set()
    first_dupe_idx = -1
    for i, char in enumerate(x_str):
        if char in seen:
            first_dupe_idx = i
            break
        seen.add(char)
    
    if first_dupe_idx == -1:
        print(x_str)
        return

    # 步骤 2: 从第一个重复位开始，从右向左回溯
    j = first_dupe_idx
    
    # 【状态优化】在这里一次性创建好 used 集合
    # set(x_str[:j]) 包含了 j 前面所有位的数字
    used_in_prefix = set(x_str[:j])
    
    while j >= 0:
        # 步骤 3: 尝试为第 j 位找到一个更大的、且未在前缀中使用的数字
        start_digit = int(x_str[j]) + 1
        for d_val in range(start_digit, 10):
            d_char = str(d_val)
            if d_char not in used_in_prefix:
                # 找到了可行的替换，立即构建并返回最终答案
                new_prefix = x_str[:j] + d_char
                
                # 步骤 4: 用干净的状态构建后缀
                used_so_far = set(new_prefix)
                suffix_list = []
                for _ in range(n - len(new_prefix)):
                    for fill_d_val in range(10):
                        fill_d_char = str(fill_d_val)
                        if fill_d_char not in used_so_far:
                            suffix_list.append(fill_d_char)
                            used_so_far.add(fill_d_char)
                            break
                
                print(new_prefix + "".join(suffix_list))
                return

        # 【状态更新】如果当前位j找不到替换，则回溯到上一位
        j -= 1
        # 高效地更新 used 集合，只需移除 j 这一位的数字
        if j >= 0:
            used_in_prefix.remove(x_str[j])

    # 步骤 5: 如果回溯到最左边也找不到替换，说明答案需要增加一位
    res = '1023456789'
    print(res[:n + 1])


if __name__ == "__main__":
    try:
        T_str = sys.stdin.readline()
        if not T_str: exit()
        T = int(T_str)
        for _ in range(T):
            line = sys.stdin.readline()
            if line:
                solve(line.strip())
    except (IOError, ValueError, IndexError):
        pass