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 math
  
  def diff_digits(x):
      
      a=[0]*10
      
      n=x
      
      while 1:
          if(n==0):
              break
          else:
              a[n%10]+=1
              n=n//10
      
      count=0
      for i in a:
          if(i>0):
              count+=1
      return [count,a]
  
  
  def check(string,k,n):
      #print('check string is: ',string)
      temp=''
      for i in string:
          temp=temp+str(i)
      
      if(diff_digits(int(temp))[0]<=k):
          return True
      else:
          return False
  
  def print_output(t_arr):
          temps=''
          for klp in t_arr:
      
              temps=temps+str(klp)
          return temps
      
  
  def strong(n_arr,t_arr,k,n,digits,i,flag):
      
      if(i>=digits):
          return True
          
  
      
      pl=int(n_arr[i])
      
  
          
      if(flag):
          for j in range(0,10):
              t_arr[i]=j
              if(check(t_arr[0:i+1],k,n)):
                  if(strong(n_arr,t_arr,k,n,digits,i+1,flag)):
                      return print_output(t_arr)
                  
      
      else:
          #print('iam here')
          for j in range(pl,10):
              t_arr[i]=j
              if(check(t_arr[0:i+1],k,n)):
                  if(strong(n_arr,t_arr,k,n,digits,i+1,flag)):
                      return print_output(t_arr)
                  
                      
              flag=True
      
      #print('t_arr is: ',t_arr)
      return False
          
      
      
  
  
  def solver(t):
      #print('inside solver')
      n=int(t[0])
      
      k=int(t[1])
      
      get=diff_digits(n)
      
      if(get[0]<=k):
          return n
      
      digits=int(math.log(n,10)) +1
      
      
      n_str=t[0]
      
      t_arr=[0]*digits
      
      return strong(n_str,t_arr,k,n,digits,0,False)
      
      
      
      
      
  
  if __name__=="__main__":
      t=int(input())
      
      z=[None]*t
      
      for i in range(t):
          z[i]=input().split(' ')
      
      for i in range(t):
          print(solver(z[i]))