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.util.*;
  import java.io.*;
  
  public class Main {
      public static void main(String args[]) {new Main().run();}
  
      FastReader in = new FastReader();
      PrintWriter out = new PrintWriter(System.out);
      void run() {
          for(int q=ni();q>0;q--){
              work();
          }
          out.flush();
      }
      long mod=998244353;
      long gcd(long a,long b) {
          return a==0?b:gcd(b%a,a);
      }
      long inf=Long.MAX_VALUE/3;
      void work() {
          long n=nl();
          int k=ni();
          List<Integer> list=new ArrayList<>();
          for(long v=n;v>0;v/=10){
              list.add((int)(v%10));
          }
          int len=list.size();
          int[] A=new int[list.size()];
          for(int i=0;i<list.size();i++){
              A[i]=list.get(list.size()-i-1);
          }
          int cnt=0;
          int[] count=new int[10];
          for(int i=0;i<len;i++){
              count[A[i]]++;
              if(count[A[i]]==1){
                  cnt++;
              }
          }
          if(cnt<=k){
              out.println(n);
              return;
          }
          for(int i=len-1;i>=0;i--){
              count[A[i]]--;
              if(count[A[i]]==0){
                  cnt--;
              }
              if(cnt==k){
                  int min=10;
                  for(int j=0;j<i;j++){
                      if(count[A[j]]>0){
                          min=Math.min(min,A[j]);
                      }
                  }
                  for(int j=1;j<=9;j++){
                      if(count[j]>0&&j>A[i]){
                          StringBuilder sb = new StringBuilder();
                          for(int p=0;p<i;p++){
                              sb.append(A[p]);
                          }
                          sb.append(j);
                          for(int p=i+1;p<len;p++){
                              sb.append(min);
                          }
                          out.println(sb.toString());
                          return;
                      }
                  }
              }else if(cnt<k){
                  StringBuilder sb = new StringBuilder();
                  for(int j=0;j<i;j++){
                      sb.append(A[j]);
                  }
                  sb.append(A[i]+1);
                  int min=0;
                  if(count[A[i]+1]==0){
                      min=A[i]+1;
                      for(int j=0;j<i;j++){
                          if(count[A[j]]>0){
                              min=Math.min(min,A[j]);
                          }
                      }
                  }
                  for(int j=i+1;j<len;j++){
                      sb.append(min);
                  }
                  out.println(sb.toString());
                  return;
              }
          }
      }
  
      @SuppressWarnings("unused")
      private ArrayList<Integer>[] ng(int n, int m) {
          ArrayList<Integer>[] graph=(ArrayList<Integer>[])new ArrayList[n];
          for(int i=0;i<n;i++) {
              graph[i]=new ArrayList<>();
          }
          for(int i=1;i<=m;i++) {
              int s=in.nextInt()-1,e=in.nextInt()-1;
              graph[s].add(e);
              graph[e].add(s);
          }
          return graph;
      }
  
      private ArrayList<long[]>[] ngw(int n, int m) {
          ArrayList<long[]>[] graph=(ArrayList<long[]>[])new ArrayList[n];
          for(int i=0;i<n;i++) {
              graph[i]=new ArrayList<>();
          }
          for(int i=1;i<=m;i++) {
              long s=in.nextLong()-1,e=in.nextLong()-1,w=in.nextLong();
              graph[(int)s].add(new long[] {e,w});
              graph[(int)e].add(new long[] {s,w});
          }
          return graph;
      }
  
      private int ni() {
          return in.nextInt();
      }
  
      private long nl() {
          return in.nextLong();
      }
      private double nd() {
          return in.nextDouble();
      }
      private String ns() {
          return in.next();
      }
  
      private long[] na(int n) {
          long[] A=new long[n];
          for(int i=0;i<n;i++) {
              A[i]=in.nextLong();
          }
          return A;
      }
  
      private int[] nia(int n) {
          int[] A=new int[n];
          for(int i=0;i<n;i++) {
              A[i]=in.nextInt();
          }
          return A;
      }
  }
  
  class FastReader
  {
      BufferedReader br;
      StringTokenizer st;
      InputStreamReader input;//no buffer
      public FastReader()
      {
          br=new BufferedReader(new InputStreamReader(System.in));
      }
  
      public FastReader(boolean isBuffer)
      {
          if(!isBuffer){
              input=new InputStreamReader(System.in);
          }else{
              br=new BufferedReader(new InputStreamReader(System.in));
          }
      }
  
      public boolean hasNext(){
          try{
              String s=br.readLine();
              if(s==null){
                  return  false;
              }
              st=new StringTokenizer(s);
          }catch(IOException e){
              e.printStackTrace();
          }
          return true;
      }
  
      public String next()
      {   
          if(input!=null){
              try {
                  StringBuilder sb=new StringBuilder();
                  int ch=input.read();
                  while(ch=='\n'||ch=='\r'||ch==32){
                      ch=input.read();
                  }
                  while(ch!='\n'&&ch!='\r'&&ch!=32){
                      sb.append((char)ch);
                      ch=input.read();
                  }
                  return sb.toString();
              }catch (Exception e){
                  e.printStackTrace();
              }
          }
          while(st==null || !st.hasMoreElements())//回车，空行情况
          {
              try {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) {
                  e.printStackTrace();
              }
          }
          return st.nextToken();
      }
  
      public int nextInt()
      {
          return (int)nextLong();
      }
  
      public long nextLong() {
          try {
              if(input!=null){
                  long ret=0;
                  int b=input.read();
                  while(b<'0'||b>'9'){
                      b=input.read();
                  }
                  while(b>='0'&&b<='9'){
                      ret=ret*10+(b-'0');
                      b=input.read();
                  }
                  return ret;
              }
          }catch (Exception e){
              e.printStackTrace();
          }
          return Long.parseLong(next());
      }
  
      public double nextDouble()
      {
          return Double.parseDouble(next());
      }
  }