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.io.BufferedReader;
  import java.io.FileReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.*;
  
  public class Main {
  
      public static void test() {
          int t = 10_000;
          Random r = new Random();
  
          long start = System.currentTimeMillis();
          StringBuilder sb = new StringBuilder();
          for (int i = 0; i < t; i++) {
              int n = r.nextInt(1_000_000_000) + 1;
              n = 127654389;
              int k = r.nextInt(10) + 1;
              k = 8;
              int x = findNext(n, k);
  //            int y = findNextBrute(n, 2);
  //            if (x != y) {
  //                System.out.println(n + " 2\n" + x + " ? " + y);
  //            }
              sb.append(x).append('\n');
          }
  //        System.out.println(sb.toString());
          System.out.println("Done: " + (System.currentTimeMillis() - start));
      }
  
      private static final int[][] bitDigits = new int[1025][];
  
      static {
          for (int i = 0; i < bitDigits.length; i++) {
              bitDigits[i] = new int[Integer.bitCount(i)];
              int pos = 0;
              for (int bit = 0; bit < 10; bit++) {
                  if ((i & (1 << bit)) != 0) {
                      bitDigits[i][pos++] = bit;
                  }
              }
          }
          Arrays.sort(bitDigits, Comparator.comparingInt(o -> o.length));
      }
  
      private static Map<Long, Integer> cache = new HashMap<>();
  
      public static void main(String[] args) throws IOException {
  
          // test();
  
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1024 * 1024 * 2);
          // br = new BufferedReader(new FileReader("src/codeforces/div3/_739/input.txt"), 1024 * 1024 * 2);
  
  
          int t = Integer.parseInt(br.readLine());
          StringBuilder sb = new StringBuilder();
          while (t-- > 0) {
              int[] v = readArrayLine(br.readLine(), 2);
              sb.append(findNext(v[0], v[1])).append("\n");
          }
  
          System.out.println(sb.toString());
      }
  
      private static int numOfDigits(long n) {
          int i = 0;
          while (n > 0) {
              n /= 10;
              i++;
          }
          return i;
      }
  
      private static int getFirstDigit(long n) {
          int d = 0;
          while (n > 0) {
              d = (int) (n % 10);
              n /= 10;
          }
          return d;
      }
  
      private static int getRepet(int digit, int n) {
          int value = 0;
          while (n-- > 0) {
              value *= 10;
              value += digit;
          }
  
          return value;
      }
  
      public static int findNext(int n, int k) {
          if (ok(n, k)) {
              return n;
          }
  
          int digits = numOfDigits(n);
          int firstDig = getFirstDigit(n);
          if (k == 1) {
              int ret = getRepet(firstDig, digits);
              if (ret < n) {
                  ret = getRepet(firstDig + 1, digits);
              }
              return ret;
          }
  
          int[] targetDigits = new int[digits];
          int p = n;
          for (int i = digits - 1; i >= 0; i--) {
              targetDigits[i] = p % 10;
              p /= 10;
          }
  
          int[] temp = new int[digits];
          long min = getRepet(9, digits);
          int bestFirstDigit = 9;
          for (int i = 1; i < bitDigits.length; i++) {
              int[] toUseDigits = bitDigits[i];
              if (toUseDigits.length > k) {
                  break;
              }
              if (toUseDigits[0] > bestFirstDigit) {
                  continue;
              }
  
              long solution = getSolution(targetDigits, toUseDigits, temp);
              if (solution < min) {
                  min = solution;
                  bestFirstDigit = getFirstDigit(min);
              }
          }
          return (int) min;
      }
  
      private static long getSolution(int[] target, int[] digits, int[] tmp) {
          solution = -1;
          getNextWithGiven(target, tmp, digits, 0);
          if (solution == -1) {
              return Integer.MAX_VALUE;
          }
          return solution;
      }
  
      private static long parse(int[] num) {
          long p = 0;
          for (int j : num) {
              p = p * 10 + j;
          }
          return p;
      }
  
      private static int solution = -1;
  
      private static void getNextWithGiven(int[] target, int[] v, int[] digits, int pos) {
          if (pos == target.length) {
              solution = (int) parse(v);
              return;
          }
  
          for (int digit : digits) {
              if (digit == target[pos]) {
                  v[pos] = digit;
                  getNextWithGiven(target, v, digits, pos + 1);
                  if (solution != -1) {
                      break;
                  }
              } else if (digit > target[pos]){
                  v[pos++] = digit;
                  while (pos < target.length) {
                      v[pos++] = digits[0];
                  }
                  solution = (int) parse(v);
                  break;
              }
  
          }
      }
  
      private static int getNextSmart(int n, int k, int mask) {
          int digits = numOfDigits(n);
          int firstDig = getFirstDigit(n);
          int digitMask = 1 << firstDig;
          int newMask = mask | digitMask;
  
          if (Integer.bitCount(newMask) <= k) {
              int elem = (int) (firstDig * Math.pow(10, digits - 1));
              return elem + getNextSmart(n - elem, k, newMask);
          } else {
              return 0;
          }
      }
  
      public static int findNextBrute(int n, int k) {
          while (!ok(n, k)) {
              n++;
          }
          return n;
      }
  
      public static boolean ok(int n, int k) {
          int digitsMask = 0;
          int digitsUsed = 0;
  
          while (n > 0) {
              int digit = n % 10;
              int mask = 1 << digit;
              if ((digitsMask & mask) == 0) {
                  digitsMask |= mask;
                  digitsUsed++;
                  if (digitsUsed > k) {
                      return false;
                  }
              }
              n /= 10;
          }
          return true;
      }
  
      public static int[] readArrayLine(String line, int n) {
          return readArrayLine(line, n, null, 0);
      }
  
      private static int[] readArrayLine(String line, int n, int array[], int pos) {
          int[] ret = array == null ? new int[n] : array;
          int start = 0;
          int end = line.indexOf(' ', start);
          for (int i = pos; i < pos + n; i++) {
              if (end > 0)
                  ret[i] = Integer.parseInt(line.substring(start, end));
              else
                  ret[i] = Integer.parseInt(line.substring(start));
              start = end + 1;
              end = line.indexOf(' ', start);
          }
          return ret;
      }
  }
  