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 itertools
  from sys import maxsize, stdout, stdin,stderr
  mod = int(1e9+7)
  import sys
  def I(): return int(stdin.readline())
  def lint(): return [int(x) for x in stdin.readline().split()]
  def S(): return list(map(str,input().strip()))
  def grid(r, c): return [lint() for i in range(r)]
  from collections import defaultdict, Counter, deque
  import math
  import heapq
  from heapq import heappop , heappush
  import bisect
  from itertools import groupby
  from itertools import permutations as comb
  def gcd(a,b): 
      while b:
          a %= b
          tmp = a
          a = b
          b = tmp
      
      return a
   
  def lcm(a,b): 
      return a  // gcd(a, b) * b
   
  def check_prime(n):
      for i in range(2, int(n ** (1 / 2)) + 1):
          if not n % i:
              return False
      return True
  
  def nCr(n, r):
   
      return (fact(n) // (fact(r)
                  * fact(n - r)))
   
  # Returns factorial of n
  def fact(n):
   
      res = 1
       
      for i in range(2, n+1):
          res = res * i
           
      return res
  def primefactors(n):
      num=0
      
      while n % 2 == 0:
          num+=1
          n = n / 2
      
      for i in range(3,int(math.sqrt(n))+1,2):
           
      
          while n % i== 0:
              num+=1
              n = n // i
                 
      
      if n > 2:
          num+=1
      return num
  '''
  def iter_ds(src):
      store=[src]
      while len(store):
          tmp=store.pop()
          if not vis[tmp]:
              vis[tmp]=True
              for j in ar[tmp]:
                  store.append(j)
  '''
  def ask(a):
      print('? {}'.format(a),flush=True)
      n=I()
      
      return n
  def linear_sieve(n):
      is_composite=[False]*n
      prime=[]
      for i in range(2,n):
          if not is_composite[i]:
              prime.append(i)
          for j in prime:
              is_composite[i*j]=True
              if i%prime==0:
                  break
      return prime
   
  def dfs(i,p,d):
      
      a,tmp=0,0
      for j in d[i]:
          if j!=p:
              a+=1
              tmp+=dfs(j,i)
      
      if a==0:
          return 0
      
      return tmp/a + 1 
  def primeFactors(n):
      l=[]
      
      while n % 2 == 0:
          l.append(2)
          n = n // 2
      for i in range(3,int(math.sqrt(n))+1,2):
           
          
          while n % i== 0:
              l.append(i)
              n = n // i
  
      if n > 2:
          l.append(n)
      return l
  from math import inf
  '''
  t = I()
  # t=1'
  
  
  for _ in range(t):
      n,k=lint()
      if k==1:
          
          tmp=str(n)
          a=len(tmp)
          if len(set(tmp))==1:
              print(tmp)
          else:
              if int(tmp[0]*a)<n:
                  if tmp[0]=='9':
                      print('1'*(a+1))
                  else:
                      print(str(int(tmp[0])+1)*a)
              else:
                  print(int(tmp[0]*a))
          
      else:
          ans=mod
          tmp=str(n)
          a=len(tmp)
          if len(set(tmp))<=2:
              
              print(int(tmp))
          else:
              if int(tmp[0]*a)<=n:
                  if tmp[0]=='9':
                      ans='1'*(a+1)
                  else:
                      ans=str(int(tmp[0])+1)*a
              else:
                  ans=int(tmp[0]*a)
              if a>=3:
  
                  b=int(tmp[1])
                  while True:
                      if int(tmp[0]+str(b)*(a-1))<n:
                          b+=1
  
  
                      else:
                          q=0
                          while q<=a-2 and int(tmp[0]+str(b)+ tmp[0]*(a-2-q)+ str(b)*q)<n:
                              q+=1
                          
                          ans2=int(tmp[0]+str(b)*q+ tmp[0]*(a-1-q))
                          break
              else:
                  ans=n
              if int(ans)<int(ans2):
                  print(ans)
              else:
                  print(ans2)
      
  '''
  t=I()
  
  l=[]
  for i in range(10):
      for j in range(10):
          
          for k in range(1,11):  
              for z in itertools.product([str(i),str(j)],repeat=k):
                  l.append(int(''.join(list(z))))   
          
                  
  # l=list(set(l))
  l.sort()
  
  for _ in range(t):
      n,k=input().split()
      k=int(k)
      n=list(map(str,n.strip()))
                         
      
  
      while True:
          
          if len(set(n)) <= k:
              print(''.join(n))
              break
  
          s=set()
          i=0
          while True:
              s.add(n[i])
              if len(s)>k:
                  while n[i]=='9':
                      i-=1
                  n[i]=str(int(n[i])+1)
  
                  for j in range(i+1,len(n)):
                      n[j]='0'
                  break
              i+=1
  
  
      
  