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: def naiveSolve(n,k):
      
      i=n
      while True:
          i2=i
          u=set()
          while i2>0:
              u.add(i2%10)
              i2//=10
          if len(u)<=k:
              return i
          i+=1
      
      return
  
  def solve(n,k):
      narr=[]
      n2=n
      while n2>0:
          narr.append(n2%10)
          n2//=10
      narr.reverse()
      
      ansarr=[]
      unique=set()
      stoppingIndex=-1
      for i,x in enumerate(narr):
          if x in unique or len(unique)+1<=k:
              ansarr.append(x)
              unique.add(x)
          else:
              stoppingIndex=i
              break
      # print(unique,stoppingIndex,ansarr)
      if stoppingIndex!=-1: # stopped
          seen=sorted(unique)
          if narr[stoppingIndex]<max(seen): # put a larger seen number
              for x in seen:
                  if x>narr[stoppingIndex]:
                      ansarr.append(x)
                      break
              while len(ansarr)<len(narr): # put smallest seen number
                  ansarr.append(min(seen))
          else:
              # narr[stoppingIndex]>max(seen). must increase some prev. number
              i=stoppingIndex-1
              while True:
                  ansarr[i]+=1
                  if ansarr[i]==10: # cannot
                      ansarr.pop()
                      i-=1
                      continue
                  if len(set(ansarr))<=k: # ok
                      break
              
              unique=set(ansarr)
              if len(unique)==k-1: # place 0s
                  remaining=0
              else: # place minimum previous
                  remaining=min(unique)
              while len(ansarr)<len(narr):
                  ansarr.append(remaining)
      ans=0
      for x in ansarr:
          ans*=10
          ans+=x
      return ans
  
  def main():
      
      t=int(input())
      allans=[]
      for _ in range(t):
          n,k=readIntArr()
          ans=solve(n,k)
          allans.append(ans)
      multiLineArrayPrint(allans)
      
      # for n in range(4000,5000):
      #     for k in range(1,11):
      #         ans=solve(n,k)
      #         ans2=naiveSolve(n,k)
      #         if ans!=ans2:
      #             print('n:{} k:{} ans:{} actualAns:{}'.format(n,k,ans,ans2))
      # print(solve(4889,2))
      
      return
  
  
  import sys
  input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
  # input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.
  
  def oneLineArrayPrint(arr):
      print(' '.join([str(x) for x in arr]))
  def multiLineArrayPrint(arr):
      print('\n'.join([str(x) for x in arr]))
  def multiLineArrayOfArraysPrint(arr):
      print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
   
  def readIntArr():
      return [int(x) for x in input().split()]
  # def readFloatArr():
  #     return [float(x) for x in input().split()]
   
  def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
      dv=defaultValFactory;da=dimensionArr
      if len(da)==1:return [dv() for _ in range(da[0])]
      else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
   
  def queryInteractive(x):
      print('{}'.format(x))
      sys.stdout.flush()
      return int(input())
   
  def answerInteractive(ans):
      print('! {}'.format(ans))
      sys.stdout.flush()
   
  inf=float('inf')
  # MOD=10**9+7
  MOD=998244353
  
  from math import gcd,floor,ceil
  # from math import floor,ceil # for Python2
   
  for _abc in range(1):
      main()