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():
      
  
      
      return
  
  def solve(n,k):
      narr=[]
      n2=n
      while n2>0:
          narr.append(n2%10)
          n2//=10
      narr.reverse()
      
      ansarr=narr.copy()
      while len(set(ansarr))>k:
          ansarr[-1]+=1
          while ansarr[-1]==10:
              ansarr.pop()
              ansarr[-1]+=1
      if len(set(ansarr))<k:
          append=0
      else:
          append=min(ansarr)
      while len(ansarr)<len(narr):
          ansarr.append(append)
          
          
      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)
      
      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()