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 java.util.*;
  
  public class Solution {
      public static boolean validate(int digit, int index, int n, int k, int[] res, Set<Integer> choose) {
          boolean isOk = false;
          if (choose.contains(digit) || choose.size() < k) {
              isOk = true;
              choose.add(digit);
          }
          if (!isOk) {
              // check if we can replace by the exist one
              for (int value : choose) {
                  if (value > digit) {
                      res[index] = value;
                      return true;
                  }
              }
              if (index < k) {
                  res[index] = digit;
                  return true;
              }
              return false;
          }
          res[index] = digit;
          return true;
      }
  
      public static  boolean validate(int[] res, int len, int k) {
          Set<Integer> chose = new HashSet<>();
          for (int i = 0; i <= len; ++i) {
              chose.add(res[i]);
          }
          return chose.size() <= k;
      }
  
      // 1771890
      public static String analyze(int n, int k) {
          String result = "";
          String s = "" + n;
          Set<Integer> choose = new HashSet<>();
          int len = s.length();
          int[] res = new int[len];
          for (int i = 0; i < len; ++i) {
              res[i] = s.charAt(i) - '0';
              if (!validate(res, i, k)) {
                  do {
                      if (res[i] == 9) {
                          i--;
                      }
                      res[i]++;
                  } while (!validate(res, i, k));
                  // fill the rest by the min value
                  int min = Integer.MAX_VALUE;
                  for (int j = 0; j <= i; ++j) {
                      if (res[j] < min) {
                          min = res[j];
                      }
                      choose.add(res[j]);
                  }
                  min = choose.size() < k ? 0 : min;
                  for (int j = i+1; j < len; ++j) {
                      res[j] = min;
                  }
                  break;
              }
          }
          for (int i = 0; i < len; ++i) {
              result += res[i];
          }
          return result;
      }
      public static void main(String[] args) {
          Scanner scanner = new Scanner(System.in);
          int testCase = scanner.nextInt();
          while (testCase-- > 0) {
              int n = scanner.nextInt();
              int k = scanner.nextInt();
              System.out.println(analyze(n, k));
          }
      }
  }
  
  