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.nio.charset.Charset;
  import java.security.MessageDigest;
  import java.security.NoSuchAlgorithmException;
  import java.util.*;
  import java.io.*;
  import static java.lang.Math.*;
  
  public class ACMIND
  {
      static FastReader scan;
      static PrintWriter pw;
      static long MOD = 1_000_000_007;
      static long INF = 2_000_000_000_000_000_000L;
      static long inf = 2_000_000_000;
      public static void main(String[] args) {
          new Thread(null,null,"_",1<<27)
          {
              public void run()
              {
                  try
                  {
                      solve();
                  }
                  catch(Exception e)
                  {
                      e.printStackTrace();
                      System.exit(1);
                  }
              }
          }.start();
      }
  
      static int min[][];
      static void solve() throws IOException {
          scan = new FastReader();
          pw = new PrintWriter(System.out, true);
          StringBuilder sb = new StringBuilder();
  
          min = new int[1024][11];
          for(int i=0;i<1024;i++) {
              for(int j=0;j<=10;j++) {
                  min[i][j] = -1;
                  for(int k=j;k<10;k++) {
                      if((i&(1<<k))!=0) {
                          min[i][j] = k;
                          break;
                      }
                  }
              }
          }
          int t = ni();
          while (t-->0) {
              int n = ni();
              int k = ni();
              long ans = Integer.MAX_VALUE;
              for(int mask=2;mask<1024;++mask) {
                  if(Integer.bitCount(mask) == k) {
                      // pl("mask: "+mask+" "+get(n, mask));
                      ans = min(ans, get(n, mask));
  
                      long res = 0;
                      int len = Integer.toString(n).length();
                      while (len-->=0) {
                          res = res*10 + min[mask][1];
                      }
                      ans = min(ans, res);
                  }
              }
              pl(ans);
  //            int actual = brute(n,k);
  //            if(ans!=actual) {
  //                pl("ERRRRR n: "+n+" k: "+k+" your: "+ans+" actu: "+actual);
  //                System.exit(1);
  //            }
          }
  
          pw.flush();
          pw.close();
      }
  
      static int brute(int n, int k) {
          for(int i=n;;i++) {
              int mask = 0;
              int x = i;
              while (x>0) {
                  mask |= (1<<(x%10));
                  x /= 10;
              }
  
              if(Integer.bitCount(mask) <= k) {
                  return i;
              }
          }
      }
  
      static long get(int n, int mask) {
          String s = Integer.toString(n);
          int len = s.length();
          boolean as = false;
          long res = 0;
          for(int i=0;i<len;i++) {
              if(as) {
                  res = res * 10 + min[mask][0];
              }
              else {
                  int d = min[mask][s.charAt(i) - '0'];
                  if(d==-1) {
                      int idx = -1;
                      for(int j=i-1;j>=0;--j) {
                          if(min[mask][s.charAt(j) - '0' + 1]!=-1) {
                              idx = j;
                              break;
                          }
                      }
  
                      if(idx==-1) {
                          return Integer.MAX_VALUE;
                      }
                      else {
                          long ans = 0;
                          for(int j=0;j<idx;j++) {
                              ans = (ans * 10 + (s.charAt(j) - '0'));
                          }
                          ans = ans * 10 + min[mask][s.charAt(idx) - '0' + 1];
                          for(int j=idx+1;j<len;j++) {
                              ans = (ans * 10 + min[mask][0]);
                          }
                          return ans;
                      }
                  }
                  else {
                      if(d>(s.charAt(i) - '0')) {
                          as = true;
                      }
                      res = res * 10 + d;
                  }
              }
          }
  
          return res;
      }
  
      static void assert_in_range(String varName, int n, int l, int r) {
          if (n >=l && n<=r) return;
          System.out.println(varName + " is not in range. Actual: "+n+" l : "+l+" r: "+r);
          System.exit(1);
      }
      static void assert_in_range(String varName, long n, long l, long r) {
          if (n>=l && n<=r) return;
          System.out.println(varName + " is not in range. Actual: "+n+" l : "+l+" r: "+r);
          System.exit(1);
      }
  
      static int ni() throws IOException
      {
          return scan.nextInt();
      }
      static long nl() throws IOException
      {
          return scan.nextLong();
      }
      static double nd() throws IOException
      {
          return scan.nextDouble();
      }
      static void pl()
      {
          pw.println();
      }
      static void p(Object o)
      {
          pw.print(o+" ");
      }
      static void pl(Object o)
      {
          pw.println(o);
      }
      static void psb(StringBuilder sb)
      {
          pw.print(sb);
      }
      static void pa(String arrayName, Set<Object> set)
      {
          pl(arrayName+" : ");
          for(Object o : set)
              p(o);
          pl();
      }
      static void pa(String arrayName, Object arr[])
      {
          pl(arrayName+" : ");
          for(Object o : arr)
              p(o);
          pl();
      }
      static void pa(String arrayName, int arr[])
      {
          pl(arrayName+" : ");
          for(int o : arr)
              p(o);
          pl();
      }
      static void pa(String arrayName, long arr[])
      {
          pl(arrayName+" : ");
          for(long o : arr)
              p(o);
          pl();
      }
      static void pa(String arrayName, double arr[])
      {
          pl(arrayName+" : ");
          for(double o : arr)
              p(o);
          pl();
      }
      static void pa(String arrayName, char arr[])
      {
          pl(arrayName+" : ");
          for(char o : arr)
              p(o);
          pl();
      }
      static void pa(String listName, List list)
      {
          pl(listName+" : ");
          for(Object o : list)
              p(o);
          pl();
      }
      static void pa(String arrayName, Object[][] arr) {
          pl(arrayName+" : ");
          for(int i=0;i<arr.length;++i) {
              for(Object o : arr[i])
                  p(o);
              pl();
          }
      }
      static void pa(String arrayName, int[][] arr) {
          pl(arrayName+" : ");
          for(int i=0;i<arr.length;++i) {
              for(int o : arr[i])
                  p(o);
              pl();
          }
      }
      static void pa(String arrayName, long[][] arr) {
          pl(arrayName+" : ");
          for(int i=0;i<arr.length;++i) {
              for(long o : arr[i])
                  p(o);
              pl();
          }
      }
      static void pa(String arrayName, char[][] arr) {
          pl(arrayName+" : ");
          for(int i=0;i<arr.length;++i) {
              for(char o : arr[i])
                  p(o);
              pl();
          }
      }
      static void pa(String arrayName, double[][] arr) {
          pl(arrayName+" : ");
          for(int i=0;i<arr.length;++i) {
              for(double o : arr[i])
                  p(o);
              pl();
          }
      }
      static class FastReader {
          final private int BUFFER_SIZE = 1 << 16;
          private DataInputStream din;
          private byte[] buffer;
          private int bufferPointer, bytesRead;
  
          public FastReader() {
              din = new DataInputStream(System.in);
              buffer = new byte[BUFFER_SIZE];
              bufferPointer = bytesRead = 0;
          }
  
          public FastReader(String file_name) throws IOException {
              din = new DataInputStream(new FileInputStream(file_name));
              buffer = new byte[BUFFER_SIZE];
              bufferPointer = bytesRead = 0;
          }
  
          public String readLine() throws IOException {
              byte[] buf = new byte[1000000];
              int cnt = 0, c;
              while ((c = read()) != -1) {
                  if (c == '\n') break;
                  buf[cnt++] = (byte) c;
              }
              return new String(buf, 0, cnt);
          }
  
          public int nextInt() throws IOException {
              int ret = 0;
              byte c = read();
              while (c <= ' ') c = read();
              boolean neg = (c == '-');
              if (neg) c = read();
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
              if (neg) return -ret;
              return ret;
          }
  
          public long nextLong() throws IOException {
              long ret = 0;
              byte c = read();
              while (c <= ' ') c = read();
              boolean neg = (c == '-');
              if (neg) c = read();
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
              if (neg) return -ret;
              return ret;
          }
  
          public double nextDouble() throws IOException {
              double ret = 0, div = 1;
              byte c = read();
              while (c <= ' ') c = read();
              boolean neg = (c == '-');
              if (neg) c = read();
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
              if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10);
              if (neg) return -ret;
              return ret;
          }
  
          private void fillBuffer() throws IOException {
              bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
              if (bytesRead == -1) buffer[0] = -1;
          }
  
          private byte read() throws IOException {
              if (bufferPointer == bytesRead) fillBuffer();
              return buffer[bufferPointer++];
          }
  
          public void close() throws IOException {
              if (din == null) return;
              din.close();
          }
      }
  }