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.OutputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.io.OutputStream;
  import java.io.PrintWriter;
  import java.util.Arrays;
  import java.io.BufferedWriter;
  import java.util.Collection;
  import java.util.InputMismatchException;
  import java.io.IOException;
  import java.util.Random;
  import java.io.Writer;
  import java.io.OutputStreamWriter;
  import java.util.NoSuchElementException;
  import java.io.InputStream;
  
  /**
   * Built using CHelper plug-in
   * Actual solution is at the top
   */
  public class Main {
      public static void main(String[] args) {
          InputStream inputStream = System.in;
          OutputStream outputStream = System.out;
          InputReader in = new InputReader(inputStream);
          OutputWriter out = new OutputWriter(outputStream);
          TaskF2 solver = new TaskF2();
          solver.solve(1, in, out);
          out.close();
      }
  
      static class TaskF2 {
          public void solve(int testNumber, InputReader in, OutputWriter out) {
              var tc = in.nextInt();
              for (int i = 0; i < tc; i++) {
                  solution(i, in, out);
              }
          }
  
          void solution(int testNumber, InputReader in, OutputWriter out) {
              int kk = in.nextInt();
              char[] k = String.valueOf(kk).toCharArray();
              int limit = in.nextInt();
              var currentDigits = new EzCharHashSet(k).size();
              if (limit >= currentDigits) {
                  out.println(k);
                  return;
              }
              char[] stt = bruteForce(k, limit);
              out.println(stt);
  
          }
  
          int getBit(int n, int k) {
              return (n >> k) & 1;
          }
  
          private char[] bruteForce(char[] k, int limit) {
              char[] minc = {9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9};
  
              for (int zz = 0; Integer.bitCount(zz) <= 10; zz++) {
                  if (Integer.bitCount(zz) == limit) {
                      char[] res = makeSmallest(k, zz);
                      if (compareArrays(res, minc) < 0) {
                          minc = res;
                      }
                  }
              }
              return minc;
          }
  
          private int nextCharSet(int bitmask, int idx) {
              for (; idx < 10; idx++) {
                  if (getBit(bitmask, idx) > 0) {
                      return idx;
                  }
              }
              return -1;
          }
  
          private char[] makeSmallest(char[] ooo, int t) {
              // makes the smallest one using this set of characters
              // lets try the simplest way, make everything set to k or higher,
              char[] z = ArrayUtils.clone(ooo);
              for (int i = 0; i < z.length; i++) {
                  char best = (char) (nextCharSet(t, z[i] - '0') + '0');
                  if (best == -1 + '0') {
                      // can't replace this one
                      // see if we can bump previous
  
                      // we're at an index of i that cannot be bumped up
                      char nnh = best;
                      for (; i >= 0 && nnh == -1 + '0'; i--) {
                          nnh = (char) (nextCharSet(t, z[i] - '0' + 1) + '0');
                      }
  
                      // can't bump up any of the previous ones, whoops
                      if (nnh == -1 + '0') {
                          // return an array 1 longer, but filled with the lowest char
                          var retArr = new char[z.length + 1];
                          // problem, char can be 0
                          Arrays.fill(retArr, (char) (nextCharSet(t, 0) + '0'));
                          char firstChar = (char) (nextCharSet(t, 0) + '0');
                          if (firstChar != -1) {
                              retArr[0] = firstChar;
                          } else {
                              Arrays.fill(retArr, 'z');
                          }
                          return retArr;
                          // just return
                      }
  
                      // can bump up a previous one.
                      // lets do it and fill it up
                      i++;
                      z[i] = nnh;
                      char ff = (char) (nextCharSet(t, 0) + '0');
                      for (int zv = i + 1; zv < z.length; zv++) {
                          z[zv] = ff;
                      }
                      return z;
                  }
  
                  //what if we can leave it as is? continue
                  if (best == z[i]) {
                      continue;
                  }
  
                  if (best > z[i]) {
                      // bumpable
                      z[i] = best;
                      char zz = (char) (nextCharSet(t, 0) + '0');
                      for (int zv = i + 1; zv < z.length; zv++) {
                          z[zv] = zz;
                      }
                      return z;
                  }
              }
              return z;
  
  
          }
  
          private int compareArrays(char[] a, char[] b) {
              if (a.length != b.length) {
                  return Integer.compare(a.length, b.length);
              }
              return Arrays.compare(a, b);
          }
  
      }
  
      static class EzCharHashSet implements EzCharSet {
          private static final int DEFAULT_CAPACITY = 8;
          private static final int HASHCODE_INITIAL_VALUE = 0x811c9dc5;
          private static final int HASHCODE_MULTIPLIER = 0x01000193;
          private static final byte FREE = 0;
          private static final byte FILLED = 2;
          private static final Random rnd = new Random();
          private static final int POS_RANDOM_SHIFT_1;
          private static final int POS_RANDOM_SHIFT_2;
          private static final int STEP_RANDOM_SHIFT_1;
          private static final int STEP_RANDOM_SHIFT_2;
          private char[] table;
          private byte[] status;
          private int size;
          private int removedCount;
          private int mask;
          private final int hashSeed;
  
          static {
              POS_RANDOM_SHIFT_1 = rnd.nextInt(10) + 11;
              POS_RANDOM_SHIFT_2 = rnd.nextInt(10) + 21;
              STEP_RANDOM_SHIFT_1 = rnd.nextInt(10) + 11;
              STEP_RANDOM_SHIFT_2 = rnd.nextInt(10) + 21;
          }
  
          public EzCharHashSet() {
              this(DEFAULT_CAPACITY);
          }
  
          public EzCharHashSet(int capacity) {
              if (capacity < 0) {
                  throw new IllegalArgumentException("Capacity must be non-negative");
              }
              // Actually we need 4x more memory
              int length = 4 * Math.max(1, capacity);
              if ((length & (length - 1)) != 0) {
                  length = Integer.highestOneBit(length) << 1;
              }
              // Length is a power of 2 now
              initEmptyTable(length);
              hashSeed = rnd.nextInt();
          }
  
          public EzCharHashSet(EzCharCollection collection) {
              this(collection.size());
              for (EzCharIterator iterator = collection.iterator(); iterator.hasNext(); ) {
                  add(iterator.next());
              }
          }
  
          public EzCharHashSet(char[] srcArray) {
              this(srcArray.length);
              for (char element : srcArray) {
                  add(element);
              }
          }
  
          public EzCharHashSet(Collection<Character> javaCollection) {
              this(javaCollection.size());
              for (char element : javaCollection) {
                  add(element);
              }
          }
  
          private int getStartPos(int h) {
              h ^= hashSeed;
              h ^= (h >>> POS_RANDOM_SHIFT_1) ^ (h >>> POS_RANDOM_SHIFT_2);
              return h & mask;
          }
  
          private int getStep(int h) {
              h ^= hashSeed;
              h ^= (h >>> STEP_RANDOM_SHIFT_1) ^ (h >>> STEP_RANDOM_SHIFT_2);
              return ((h << 1) | 1) & mask;
          }
  
          public int size() {
              return size;
          }
  
          public boolean contains(char element) {
              final int elementHash = PrimitiveHashCalculator.getHash(element);
              int pos = getStartPos(elementHash);
              final int step = getStep(elementHash);
              for (; status[pos] != FREE; pos = (pos + step) & mask) {
                  if (status[pos] == FILLED && table[pos] == element) {
                      return true;
                  }
              }
              return false;
          }
  
          public EzCharIterator iterator() {
              return new EzCharHashSetIterator();
          }
  
          public char[] toArray() {
              char[] result = new char[size];
              for (int i = 0, j = 0; i < table.length; i++) {
                  if (status[i] == FILLED) {
                      result[j++] = table[i];
                  }
              }
              return result;
          }
  
          public boolean add(char element) {
              final int elementHash = PrimitiveHashCalculator.getHash(element);
              int pos = getStartPos(elementHash);
              final int step = getStep(elementHash);
              for (; status[pos] == FILLED; pos = (pos + step) & mask) {
                  if (table[pos] == element) {
                      return false;
                  }
              }
              if (status[pos] == FREE) {
                  status[pos] = FILLED;
                  table[pos] = element;
                  size++;
                  if ((size + removedCount) * 2 > table.length) {
                      rebuild(table.length * 2); // enlarge the table
                  }
                  return true;
              }
              final int removedPos = pos;
              for (pos = (pos + step) & mask; status[pos] != FREE; pos = (pos + step) & mask) {
                  if (status[pos] == FILLED && table[pos] == element) {
                      return false;
                  }
              }
              status[removedPos] = FILLED;
              table[removedPos] = element;
              size++;
              removedCount--;
              return true;
          }
  
          private void rebuild(int newLength) {
              char[] oldTable = table;
              byte[] oldStatus = status;
              initEmptyTable(newLength);
              for (int i = 0; i < oldTable.length; i++) {
                  if (oldStatus[i] == FILLED) {
                      add(oldTable[i]);
                  }
              }
          }
  
          private void initEmptyTable(int length) {
              table = new char[length];
              status = new byte[length];
              size = 0;
              removedCount = 0;
              mask = length - 1;
          }
  
          public boolean equals(Object o) {
              if (this == o) return true;
              if (o == null || getClass() != o.getClass()) return false;
              EzCharHashSet that = (EzCharHashSet) o;
  
              if (size != that.size) {
                  return false;
              }
              for (int i = 0; i < table.length; i++) {
                  if (status[i] == FILLED) {
                      if (!that.contains(table[i])) {
                          return false;
                      }
                  }
              }
              return true;
          }
  
          public int hashCode() {
              char[] array = toArray();
              EzCharSort.sort(array);
              int hash = HASHCODE_INITIAL_VALUE;
              for (int i = 0; i < size; i++) {
                  hash = (hash ^ PrimitiveHashCalculator.getHash(array[i])) * HASHCODE_MULTIPLIER;
              }
              return hash;
          }
  
          public String toString() {
              StringBuilder sb = new StringBuilder();
              sb.append('[');
              for (int i = 0; i < table.length; i++) {
                  if (status[i] == FILLED) {
                      if (sb.length() > 1) {
                          sb.append(", ");
                      }
                      sb.append(table[i]);
                  }
              }
              sb.append(']');
              return sb.toString();
          }
  
          private class EzCharHashSetIterator implements EzCharIterator {
              private int curIndex = 0;
  
              public boolean hasNext() {
                  while (curIndex < table.length && status[curIndex] != FILLED) {
                      curIndex++;
                  }
                  return curIndex < table.length;
              }
  
              public char next() {
                  while (curIndex < table.length && status[curIndex] != FILLED) {
                      curIndex++;
                  }
                  if (curIndex == table.length) {
                      throw new NoSuchElementException("Iterator doesn't have more elements");
                  }
                  return table[curIndex++];
              }
  
          }
  
      }
  
      static class InputReader {
          private InputStream stream;
          private byte[] buf = new byte[1024];
          private int curChar;
          private int numChars;
          private InputReader.SpaceCharFilter filter;
  
          public InputReader(InputStream stream) {
              this.stream = stream;
          }
  
          public int read() {
              if (numChars == -1) {
                  throw new InputMismatchException();
              }
              if (curChar >= numChars) {
                  curChar = 0;
                  try {
                      numChars = stream.read(buf);
                  } catch (IOException e) {
                      throw new InputMismatchException();
                  }
                  if (numChars <= 0) {
                      return -1;
                  }
              }
              return buf[curChar++];
          }
  
          public int nextInt() {
              int c = read();
              while (isSpaceChar(c)) {
                  c = read();
              }
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              int res = 0;
              do {
                  if (c < '0' || c > '9') {
                      throw new InputMismatchException();
                  }
                  res *= 10;
                  res += c - '0';
                  c = read();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public boolean isSpaceChar(int c) {
              if (filter != null) {
                  return filter.isSpaceChar(c);
              }
              return isWhitespace(c);
          }
  
          public static boolean isWhitespace(int c) {
              return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
          }
  
          public interface SpaceCharFilter {
              public boolean isSpaceChar(int ch);
  
          }
  
      }
  
      static final class PrimitiveHashCalculator {
          private PrimitiveHashCalculator() {
          }
  
          public static int getHash(char x) {
              return x;
          }
  
      }
  
      static interface EzCharCollection {
          int size();
  
          EzCharIterator iterator();
  
          boolean equals(Object object);
  
          int hashCode();
  
          String toString();
  
      }
  
      static final class EzCharSort {
          private static final double HEAPSORT_DEPTH_COEFFICIENT = 2.0;
          private static final Random rnd = new Random();
  
          private EzCharSort() {
          }
  
          private static int maxQuickSortDepth(int length) {
              if (length <= 1) {
                  return 0;
              }
              int log = Integer.numberOfTrailingZeros(Integer.highestOneBit(length - 1)) + 1;
              return (int) (HEAPSORT_DEPTH_COEFFICIENT * log);
          }
  
          public static void sort(char[] a) {
              quickSort(a, 0, a.length, 0, maxQuickSortDepth(a.length));
          }
  
          private static void quickSort(char[] a, int left, int right, int depth, int maxDepth) {
              if (right - left <= 1) {
                  return;
              }
              if (depth > maxDepth) {
                  heapSort(a, left, right - left);
                  return;
              }
              final char pivot = a[left + rnd.nextInt(right - left)];
              int i = left;
              int j = right - 1;
              do {
                  while (a[i] < pivot) i++;
                  while (pivot < a[j]) j--;
                  if (i <= j) {
                      char tmp = a[i];
                      a[i++] = a[j];
                      a[j--] = tmp;
                  }
              } while (i <= j);
              quickSort(a, left, j + 1, depth + 1, maxDepth);
              quickSort(a, i, right, depth + 1, maxDepth);
          }
  
          private static void heapSort(char[] a, int offset, int size) {
              // If size <= 1, nothing is executed
              for (int i = (size >>> 1) - 1; i >= 0; i--) {
                  down(a, i, offset, size);
              }
              for (int i = size - 1; i > 0; i--) {
                  char tmp = a[offset];
                  a[offset] = a[offset + i];
                  a[offset + i] = tmp;
                  down(a, 0, offset, i);
              }
          }
  
          private static void down(char[] a, int index, int offset, int size) {
              final char element = a[offset + index];
              final int firstLeaf = (size >>> 1);
              while (index < firstLeaf) {
                  int largestChild = (index << 1) + 1;
                  if (largestChild + 1 < size && a[offset + largestChild + 1] > a[offset + largestChild]) {
                      largestChild++;
                  }
                  if (a[offset + largestChild] <= element) {
                      break;
                  }
                  a[offset + index] = a[offset + largestChild];
                  index = largestChild;
              }
              a[offset + index] = element;
          }
  
      }
  
      static class OutputWriter {
          private final PrintWriter writer;
  
          public OutputWriter(OutputStream outputStream) {
              writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
          }
  
          public OutputWriter(Writer writer) {
              this.writer = new PrintWriter(writer);
          }
  
          public void println(char[] array) {
              writer.println(array);
          }
  
          public void close() {
              writer.close();
          }
  
      }
  
      static interface EzCharSet extends EzCharCollection {
          int size();
  
          EzCharIterator iterator();
  
          boolean equals(Object object);
  
          int hashCode();
  
          String toString();
  
      }
  
      static interface EzCharIterator {
          boolean hasNext();
  
          char next();
  
      }
  
      static class ArrayUtils {
          public static char[] clone(final char[] array) {
              if (array == null) {
                  return null;
              }
              return array.clone();
          }
  
          public ArrayUtils() {
          }
  
      }
  }
  
  