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.*;
  import java.util.HashSet;
  
  public class f2 {
      static class InputReader {
          private static final int DEFAULT_BUFFER_SIZE = 1 << 16; // Change this to increase your input size //
          private static final InputStream DEFAULT_STREAM = System.in;
          private static final int MAX_DECIMAL_PRECISION = 21;
          private int c;
          private byte[] buf;
          private int bufferSize, bufIndex, numBytesRead;
          private InputStream stream;
          private static final byte EOF = -1;
          private static final byte NEW_LINE = 10;
          private static final byte CARRIAGE_RETURN = 13;
          private static final byte SPACE = 32;
          private static final byte DASH = 45;
          private static final byte DOT = 46;
          private char[] charBuffer;
          private static byte[] bytes = new byte[58];
          private static int[] ints = new int[58];
          private static char[] chars = new char[128];
  
          static {
              char ch = ' ';
              int value = 0;
              byte _byte = 0;
              for (int i = 48; i < 58; i++) bytes[i] = _byte++;
              for (int i = 48; i < 58; i++) ints[i] = value++;
              for (int i = 32; i < 128; i++) chars[i] = ch++;
          }
  
          public InputReader() {
              this(DEFAULT_STREAM, DEFAULT_BUFFER_SIZE);
          }
  
          public InputReader(int bufferSize) {
              this(DEFAULT_STREAM, bufferSize);
          }
  
          public InputReader(InputStream stream) {
              this(stream, DEFAULT_BUFFER_SIZE);
          }
  
          public InputReader(InputStream stream, int bufferSize) {
              if (stream == null || bufferSize <= 0) throw new IllegalArgumentException();
              buf = new byte[bufferSize];
              charBuffer = new char[128];
              this.bufferSize = bufferSize;
              this.stream = stream;
          }
  
          private byte read() throws IOException {
              if (numBytesRead == EOF) throw new IOException();
              if (bufIndex >= numBytesRead) {
                  bufIndex = 0;
                  numBytesRead = stream.read(buf);
                  if (numBytesRead == EOF) return EOF;
              }
              return buf[bufIndex++];
          }
  
          private int readJunk(int token) throws IOException {
              if (numBytesRead == EOF) return EOF;
              do {
                  while (bufIndex < numBytesRead) {
                      if (buf[bufIndex] > token) return 0;
                      bufIndex++;
                  }
                  numBytesRead = stream.read(buf);
                  if (numBytesRead == EOF) return EOF;
                  bufIndex = 0;
              } while (true);
          }
  
          public byte nextByte() throws IOException {
              return (byte) ni();
          }
  
          public int ni() throws IOException {
              if (readJunk(DASH - 1) == EOF) throw new IOException();
              int sgn = 1, res = 0;
              c = buf[bufIndex];
              if (c == DASH) {
                  sgn = -1;
                  bufIndex++;
              }
              do {
                  while (bufIndex < numBytesRead) {
                      if (buf[bufIndex] > SPACE) {
                          res = (res << 3) + (res << 1);
                          res += ints[buf[bufIndex++]];
                      } else {
                          bufIndex++;
                          return res * sgn;
                      }
                  }
                  numBytesRead = stream.read(buf);
                  if (numBytesRead == EOF) return res * sgn;
                  bufIndex = 0;
              } while (true);
          }
  
          public long nl() throws IOException {
              if (readJunk(DASH - 1) == EOF) throw new IOException();
              int sgn = 1;
              long res = 0L;
              c = buf[bufIndex];
              if (c == DASH) {
                  sgn = -1;
                  bufIndex++;
              }
              do {
                  while (bufIndex < numBytesRead) {
                      if (buf[bufIndex] > SPACE) {
                          res = (res << 3) + (res << 1);
                          res += ints[buf[bufIndex++]];
                      } else {
                          bufIndex++;
                          return res * sgn;
                      }
                  }
                  numBytesRead = stream.read(buf);
                  if (numBytesRead == EOF) return res * sgn;
                  bufIndex = 0;
              } while (true);
          }
  
          private void doubleCharBufferSize() {
              char[] newBuffer = new char[charBuffer.length << 1];
              for (int i = 0; i < charBuffer.length; i++) newBuffer[i] = charBuffer[i];
              charBuffer = newBuffer;
          }
  
          public String nli() throws IOException {
              try {
                  c = read();
              } catch (IOException e) {
                  return null;
              }
              if (c == NEW_LINE) return "";
              if (c == EOF) return null;
              int i = 0;
              charBuffer[i++] = (char) c;
              do {
                  while (bufIndex < numBytesRead) {
                      if (buf[bufIndex] != NEW_LINE && buf[bufIndex] != CARRIAGE_RETURN) {
                          if (i == charBuffer.length) doubleCharBufferSize();
                          charBuffer[i++] = (char) buf[bufIndex++];
                      } else {
                          if (buf[bufIndex] == CARRIAGE_RETURN) bufIndex++;
                          bufIndex++;
                          return new String(charBuffer, 0, i);
                      }
                  }
                  numBytesRead = stream.read(buf);
                  if (numBytesRead == EOF) return new String(charBuffer, 0, i);
                  bufIndex = 0;
              } while (true);
          }
  
          public String ns() throws IOException {
              if (numBytesRead == EOF) return null;
              if (readJunk(SPACE) == EOF) return null;
              for (int i = 0; ; ) {
                  while (bufIndex < numBytesRead) {
                      if (buf[bufIndex] > SPACE) {
                          if (i == charBuffer.length) doubleCharBufferSize();
                          charBuffer[i++] = (char) buf[bufIndex++];
                      } else {
                          bufIndex++;
                          return new String(charBuffer, 0, i);
                      }
                  }
                  numBytesRead = stream.read(buf);
                  if (numBytesRead == EOF) return new String(charBuffer, 0, i);
                  bufIndex = 0;
              }
          }
  
          public double nd() throws IOException {
              String doubleVal = ns();
              if (doubleVal == null) throw new IOException();
              return Double.valueOf(doubleVal);
          }
  
          public void close() throws IOException {
              stream.close();
          }
      }
  
      // region variables
      static InputReader sc = new InputReader();
      static OutputStream outputStream = System.out;
      static PrintWriter w = new PrintWriter(outputStream);
      // endregion
  
      private static void initiateIO()
              throws IOException {
          if (System.getProperty("ONLINE_JUDGE") == null) {
              try {
                  w = new PrintWriter("output.txt");
                  sc = new InputReader(new FileInputStream("input.txt"));
              } catch (Exception e) {
                  throw new IOException();
              }
          }
      }
  
      public static void main(String[] args)
              throws IOException {
  
          initiateIO();
  
          int t = sc.ni();
          while (t-- > 0)
              solve();
  
          w.close();
  
      }
  
      static boolean check(int[] arr, int k) {
          HashSet<Integer> hs = new HashSet<>();
          for (int i = 0; i < arr.length; i++) {
              hs.add(arr[i]);
          }
          return hs.size()<=k;
      }
  
      static void solve() throws IOException {
          char[] str = sc.ns().toCharArray();
          int k = sc.ni();
          int[] arr = new int[str.length];
          HashSet<Integer> hs = new HashSet<>();
          for (int i = 0; i < str.length; i++) {
              hs.add(Integer.parseInt(str[i] + ""));
              arr[i] = Integer.parseInt(str[i]+"");
          }
          if (hs.size() <= k) {
              for (int i = 0; i < str.length; i++) {
                  w.print(str[i]);
              }
              w.println();
              return;
          }
          while (!check(arr, k)) {
              HashSet<Integer> currh = new HashSet<>();
              for (int i = 0; i < arr.length; i++) {
                  currh.add(arr[i]);
                  if(currh.size() > k) {
                      if(i < arr.length-1 && arr[i+1] == arr[i]) continue;
                      while(i >= 0) {
                          if(arr[i] != 9) {
                              arr[i]++;
                              break;
                          }else i--;
                      }
                      for (int j = i+1; j < arr.length; j++) {
                          arr[j] = 0;
                      }
                      break;
                  }
              }
          }
  
          for (int i = 0; i < arr.length; i++) {
              w.print(arr[i]);
          }
          w.println();
      }
  }