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.Scanner;
  
  public class F {
      static long[][][][] dp = new long[15][1 << 10][2][11];
  
      static long cal(int i, int mask, int zero, int k) {
          if (i >= 11) {
              if (Integer.bitCount(mask) <= k)
                  return 1L;
              return 0L;
          }
          if (dp[i][mask][zero][k] != -1)
              return dp[i][mask][zero][k];
          dp[i][mask][zero][k] = 0;
          for (int digit = 0; digit < 10; ++digit) {
              int newZero = zero;
              if (digit > 0) newZero = 1;
              if (newZero == 1)
                  dp[i][mask][zero][k] += cal(i + 1, mask | (1 << digit), 1, k);
              else 
                  dp[i][mask][zero][k] += cal(i + 1, mask, 0, k);
          }
          return dp[i][mask][zero][k];
      }
  
      static long findIndex(long num, int k) {
          long idx = 0;
          String digit = String.format("%010d", num);
          // System.out.println(digit);
          int mask = 0;
          boolean flag = false;
          for (int i = 1; i <= digit.length(); ++i) {
              for (int d = 0; d < digit.charAt(i - 1) - '0'; ++d) {
                  boolean newFlag = flag | (d > 0);
                  if (newFlag) 
                      idx += cal(i + 1, mask | (1 << d), 1, k);
                  else 
                      idx += cal(i + 1, mask, 0, k);
              }
              flag |= digit.charAt(i - 1) > '0';
              if (flag) {
                  mask |= 1 << (digit.charAt(i - 1) - '0');
  
              }
          }
          if (Integer.bitCount(mask) <= k)
              idx += 1;
          // System.out.println(Integer.bitCount(mask) + " " + k);
          // System.out.println(digit);
          // System.out.println(num + " " + idx);
          return idx;
      }
  
      static void solve(long n, int k) {
          if (findIndex(n - 1, k) != findIndex(n, k)) {
              System.out.println(n);
          } else {
              
              long idx = findIndex(n, k);
              long low = n + 1, high = (long)1e10;
              long ans = 0;
              while (low <= high) {
                  long mid = low + high >> 1;
                  if (findIndex(mid, k) > idx) {
                      ans = mid;
                      // System.out.print(mid + " " + findIndex(mid, k));
                      // System.out.println();
                      high = mid - 1;
                  } else {
                      low = mid + 1;
                  }
              }
              System.out.println(ans);
          }
      }
  
      public static void main(String[] args) {
          for (int i = 0; i <= 11; ++i) 
              for (int mask = 0; mask < (1 << 10); ++mask)
                  for (int k = 0; k <= 10; ++k)
                      dp[i][mask][0][k] = dp[i][mask][1][k] = -1;
          
          Scanner reader = new Scanner(System.in);
          int TC = reader.nextInt();
          while (TC-- > 0) {
              int n = reader.nextInt();
              int k = reader.nextInt();
              solve(n, k);
          }
          reader.close();
      }
  }