description: It is a complicated version of problem F1. The difference between them is the constraints (F1: k ≤ 2, F2: k ≤ 10).
  
  You are given an integer n. Find the minimum integer x such that x ≥ n and the number x is k-beautiful.
  
  A number is called k-beautiful if its decimal representation having no leading zeroes contains no more than k different digits. E.g. if k = 2, the numbers 3434443, 55550, 777 and 21 are k-beautiful whereas the numbers 120, 445435 and 998244353 are not.
  
  Input
  
  The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.
  
  Each test case consists of one line containing two integers n and k (1 ≤ n ≤ 10^9, 1 ≤ k ≤ 10).
  
  Output
  
  For each test case output on a separate line x — the minimum k-beautiful integer such that x ≥ n.
  
  Example
  
  Input
  
  
  6
  2021 3
  177890 2
  34512 3
  724533 4
  998244353 1
  12345678 10
  
  
  Output
  
  
  2021
  181111
  34533
  724542
  999999999
  12345678
solution: import com.sun.source.tree.Tree;
  
  import java.io.*;
  import java.math.*;
  import java.util.*;
  
  public class G {
  
      static final int MAX_N = 1000010;
      static final int INF = 0x3f3f3f3f;
  
      public static void main(String[] args) throws IOException {
  
          initReader(System.in);
  
  
          int T = nextInt();
          for (int i = 1; i <= T; i++)
          solve();
  
  
          pw.flush();
      }
  
      /*******************************************************************************************************************************/
  
  
  
      public static void solve() throws IOException {
          int n = nextInt();
          int k = nextInt();
  
          char[] num = String.valueOf(n).toCharArray();
  
          TreeSet<Integer> set = new TreeSet<>();
  
          for (char i : num) set.add(i - '0');
  
          if (set.size() <= k) {
              pw.println(n);
              return ;
          }
  
          set.clear();
          for (char i : num) {
              if (set.size() == k - 1) break;
              set.add(i - '0');
          }
  
  
  
          long ans = Long.MAX_VALUE;
          for (int i = 0; i < 10; i++) {
              TreeSet<Integer> set1 = new TreeSet<>(set);
              set1.add(i);
              ans = Math.min(ans, fun(set1, num, n, 0));
          }
  
          pw.println(ans);
      }
  
      public static long fun(TreeSet<Integer> set, char[] num, int n, int step) {
          if (step == num.length) return Long.MAX_VALUE;
  
          long res = Long.MAX_VALUE;
  
          char[] ans = new char[num.length];
          System.arraycopy(num, 0, ans, 0, step);
  
          if (set.higher(num[step] - '0') != null) {
              ans[step] = (char) (set.higher(num[step] - '0') + '0');
              for (int i = step + 1; i < num.length; i++)  ans[i] = (char) (set.first() + '0');
  
              long re = Long.parseLong(String.valueOf(ans));
              if (re >= n) res = Math.min(res, re);
          }
  
          if (set.contains(num[step] - '0')) res = Math.min(res, fun(set, num, n, step + 1));
  
  
          return res;
      }
  
  
  
      /*******************************************************************************************************************************/
  
  
  
      /*******************************************************************************************************************************/
  
      static BufferedReader reader;
      static StringTokenizer tokenizer;
      static PrintWriter pw;
  
      public static void initReader(InputStream input) throws IOException {
          reader = new BufferedReader(new InputStreamReader(input));
          tokenizer = new StringTokenizer("");
          pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  
  //        reader = new BufferedReader(new FileReader("test.in"));
  //        tokenizer = new StringTokenizer("");
  //        pw = new PrintWriter(new BufferedWriter(new FileWriter("test1.out")));
      }
  
      public static boolean hasNext() {
          try {
              while (!tokenizer.hasMoreTokens()) {
                  tokenizer = new StringTokenizer(reader.readLine());
              }
          } catch (Exception e) {
              return false;
          }
          return true;
      }
  
      public static String next() throws IOException {
          while (!tokenizer.hasMoreTokens()) {
              tokenizer = new StringTokenizer(reader.readLine());
          }
          return tokenizer.nextToken();
      }
  
      public static String nextLine() {
          try {
              return reader.readLine();
          } catch (Exception e) {
              return null;
          }
      }
  
      public static int nextInt() throws IOException {
          return Integer.parseInt(next());
      }
  
      public static long nextLong() throws IOException {
          return Long.parseLong(next());
      }
  
      public static double nextDouble() throws IOException {
          return Double.parseDouble(next());
      }
  
      public static char nextChar() throws IOException {
          return next().charAt(0);
      }
  
      public static short nextShort() throws IOException {
          return Short.parseShort(next());
      }
  
  }
  