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
  {
      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; 
          } 
      }
      //static final long mod=(long)1e9+7;
      static final long mod=998244353L;
      public static long pow(long a,long p)
      {
          long res=1;
          while(p>0)
          {
              if(p%2==1)
              {
                  p--;
                  res*=a;
                  res%=mod;
              }
              else
              {
                  a*=a;
                  a%=mod;
                  p/=2;
              }
          }
          return res;
      }
      /*static class Pair
      {
          int u,v;
          Pair(int u,int v)
          {
              this.u=u;
              this.v=v;
          }
      }*/
      /*static class Pair implements Comparable<Pair>
      {
          int v,l;
          Pair(int v,int l)
          {
              this.v=v;
              this.l=l;
          }
          public int compareTo(Pair p)
          {
              return l-p.l; 
          }
      }*/
      static long gcd(long a,long b)
      {
          if(b%a==0)
          return a;
          return gcd(b%a,a);
      }
      public static void dfs(int u,ArrayList<Integer> edge[],boolean vis[])
      {
          vis[u]=true;
          for(int v:edge[u])
          {
              if(!vis[v])
              dfs(v,edge,vis);
          }
      }
      static class DSU
      {
          int par[],rank[],n;
          DSU(int n)
          {
              this.n=n;
              par=new int[n+1];
              rank=new int[n+1];
              for(int i=1;i<=n;i++)
              par[i]=i;
          }
          public void union(int u,int v)
          {
              u=find(u);
              v=find(v);
              if(u==v)
              return;
              if(rank[u]>rank[v])
              par[v]=u;
              else if(rank[u]<rank[v])
              par[u]=v;
              else
              {
                  rank[v]++;
                  par[u]=v;
              }
          }
          public int find(int u)
          {
              if(u==par[u])
              return u;
              return par[u]=find(par[u]);
          }
      }
      static class Edge 
      {
          int v,ind;
          long w;
          Edge(int v,int w,int ind)
          {
              this.ind=ind;
              this.v=v;
              this.w=1L*w;
          }
      }
      static class Pair implements Comparable<Pair>
      {
          Edge e;
          long d;
          Pair(Edge e,long d)
          {
              this.e=e;
              this.d=d;
          }
          public int compareTo(Pair p)
          {
              if(this.d!=p.d)
              {
                  if(this.d<=p.d)
                  return -1;
                  return 1;
              }
              if(this.e.w<=p.e.w)
              return -1;
              return 1;
          }
      }
      public static void main(String args[])throws Exception
      {
          FastReader fs=new FastReader();
          PrintWriter pw=new PrintWriter(System.out);
          int tc=fs.nextInt();
          while(tc-->0)
          {
              int num=fs.nextInt();
              int k=fs.nextInt();
              char c[]=Integer.toString(num).toCharArray();
              int n=c.length;
              TreeSet<Integer> ts=new TreeSet<>();
              int i,last=-1;
              int cnt[]=new int[10];
              for(i=0;i<n;i++)
              {
                  if(ts.size()==k)break;
                  if(!ts.contains(c[i]-'a'))
                  last=i;
                  cnt[c[i]-'0']++;
                  ts.add(c[i]-'0');
              }
              while(i<n&&ts.contains(c[i]-'0'))
              {
                  cnt[c[i]-'0']++;
                  i++;
              }
              int tot[]=new int[10];
              for(int j=0;j<10;j++)
              tot[j]=cnt[j];
              if(i==n)
              pw.println(num);
              else
              {
                  int ind=-1;
                  int tt=c[i]-'0';
                  if(ts.ceiling(tt+1)!=null)
                  {
                      int ceil=ts.ceiling(tt+1);
                      c[i]=(char)(ceil+'0');
                      ceil=ts.first();
                      i++;
                      while(i<n)
                      {
                          c[i]=(char)(ceil+'0');
                          i++;
                      }
                  }
                  else
                  {
                      --i;
                      while(i>=0)
                      {
                          if(cnt[c[i]-'0']==1)
                          {
                              ts.remove(c[i]-'0');
                              c[i]=(char)(c[i]+1);
                              ts.add(c[i]-'0');
                              ++i;
                              break;
                          }
                          if(ts.ceiling((c[i]-'0')+1)!=null)
                          {
                              int nn=ts.ceiling((c[i]-'0')+1);
                              if(tot[c[i]-'0']==1)
                              ts.remove(c[i]-'0');
                              c[i]=(char)(nn+'0');
                              ++i;
                              break;
                          }
                          cnt[c[i]-'0']--;
                          --i;
                      }
                      if(ts.size()!=k)
                      ts.add(0);
                      while(i<n)
                      {
                          c[i]=(char)(ts.first()+'0');
                          i++;
                      }
                  }
                  pw.println(new String(c));
              }
          }
          pw.flush();
          pw.close();
      }
  }