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.*;
  public class Main {
      public static void main(String args[])
      {
          FastReader input=new FastReader();
          PrintWriter out=new PrintWriter(System.out);
          int T=input.nextInt();
          while(T-->0)
          {
              int n=input.nextInt();
              int k=input.nextInt();
              String s=String.valueOf(n);
              int arr[]=new int[10];
              for(int i=0;i<s.length();i++)
              {
                  int v=s.charAt(i)-'0';
                  arr[v]++;
              }
              if(fun(arr,k))
              {
                  out.println(n);
              }
              else
              {
                  int x=0,y=0,z=0;
                  for(int i=s.length()-1;i>=0;i--)
                  {
                      int v=s.charAt(i)-'0';
                      arr[v]--;
                      int f=0;
                      for(int j=v+1;j<10;j++)
                      {
                          arr[j]++;
                          if(i+1<s.length())
                          {
                              for(int l=0;l<10;l++)
                              {
                                  arr[l]++;
                                  if(fun(arr,k))
                                  {
                                      x=i;y=j;z=l;
                                      f=1;
                                      break;
                                  }
                                  arr[l]--;
                              }
                          }
                          else
                          {
                              if(fun(arr,k))
                              {
                                  x=i;y=j;
                                  f=1;
                                  break;
                              }
                          }
                          if(f==1) break;
                          arr[j]--;
                      }
                      if(f==1) break;
                  }
                  String ans="";
                  for(int i=0;i<x;i++)
                  {
                      ans+=s.charAt(i);
                  }
                  ans+=y;
                  for(int i=x+1;i<s.length();i++)
                  {
                      ans+=z;
                  }
                  out.println(ans);
              }
          }
          out.close();
      }
      public static boolean fun(int arr[],int k)
      {
          int c=0;
          for(int i=0;i<10;i++)
          {
              if(arr[i]>0)
              {
                  c++;
              }
          }
          if(c<=k)
          {
              return true;
          }
          return false;
      }
      static class FastReader
      {
          BufferedReader br;
          StringTokenizer st;
          public FastReader()
          {
              br = new BufferedReader(new InputStreamReader(System.in));
          }
          String next()
          {
              while (st == null || !st.hasMoreElements())
              {
                  try
                  {
                      st = new StringTokenizer(br.readLine());
                  }
                  catch (IOException e)
                  {
                      e.printStackTrace();
                  }
              }
              return st.nextToken();
          }
          int nextInt()
          {
              return Integer.parseInt(next());
          }
          long nextLong()
          {
              return Long.parseLong(next());
          }
          double nextDouble()
          {
              return Double.parseDouble(next());
          }
          String nextLine()
          {
              String str="";
              try
              {
                  str=br.readLine();
              }
              catch (IOException e)
              {
                  e.printStackTrace();
              }
              return str;
          }
      }
  }