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 one(n: str, lili: dict):
    
    sel = n[0]
    def have_greater_in_lili_or_sel(digit: str) -> bool:
      for li, exists in lili.items():
        if exists and li > digit:
          return True
      return sel > digit
    
    for digit in n[1:]:
      # if the digit is less than sel or we already have a greater digit.
      if have_greater_in_lili_or_sel(digit):
        # we have a safe tight choice.
        break
      # if we already have that digit, continue.
      if digit in [d for d in lili if lili[d]]:
        continue
      # if the digit is greater than sel and we don't have the digit or a greater one.
      if digit > sel:
        sel = str(int(sel) + 1)
        # if we already has dat digit(sel+1), we still got a spare k.
        if lili[sel]:
          # Set the lowest value to true then.
          lili['0'] = True
        break
    lili[sel] = True
  
  def run(n: str, k: int, lili: dict):
    if not n or not k:
      return
    elif lili[n[0]]:
      run(n[1:], k, lili)
    elif k == 1:
      one(n, lili)
    else:
      lili[n[0]] = True
      run(n[1:], k - 1, lili)
  
  def clean(n: str, lili: dict) -> str:
    
    def least_greater(n_dig: str, res_dig: str) -> str:
      best = res_dig
      for digit, exists in lili.items():
        if exists and digit > n_dig:
          best = min(best, digit)
      return best
    
    maybe_a_better_resut = ''
    min_dig = min(digit for digit in '0123456789' if lili[digit])
    max_dig = max(digit for digit in '0123456789' if lili[digit])
    for curr_index, n_dig in enumerate(n):
      best = least_greater(str(int(n_dig) - 1) , max_dig)
      if best > n_dig:
        # If the best is bigger than the number itself,
        # add it and fill the rest with the min_val we have.
        maybe_a_better_resut += best
        for _ in range(len(n) - curr_index - 1):
          maybe_a_better_resut += min_dig
        break
      elif best < n_dig:
        parent = maybe_a_better_resut[curr_index - 1]
        # If the best was smaller than the number itslef,
        # then we have to set our parent to a greater value
        # and fill the rest with min_val.
        maybe_a_better_resut = (
            # for the record, this is just doing:
            # maybe_a_better_result[curr_index - 1] = least_greater(maybe_a_better_resut[curr_index - 1],  max_dig)
            maybe_a_better_resut[:curr_index - 1]
            +
            least_greater(
                maybe_a_better_resut[curr_index - 1],
                max_dig)
          )
        if parent == maybe_a_better_resut[curr_index - 1]:
          n = (
              n[:curr_index - 1]
              +
              str(int(parent) + 1) #lets hope parent != '9' :(
              +
              n[curr_index:]
          )
          return clean(n, lili)
        for _ in range(len(n) - curr_index):
          maybe_a_better_resut += min_dig
        break
      # if best == n_dig
      else:
        maybe_a_better_resut += best
        
    return maybe_a_better_resut
  
  t = int(input())
  for i in range(1, t + 1):
    n, k = input().split()
    lili = {digit: False for digit in '0123456789'}
    if len(set(n)) == int(k):
      print(n)
      continue
    run(n, int(k), lili)
    result = clean(n, lili)
    # if result == '101000000' and i == 1703:
    #   print(n+'-'+k)
    #   continue
    print(result)
    