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 collections as _collections
  import itertools as _itertools
  import sys as _sys
  
  
  def _main():
      [tests_n] = _read_ints()
      for i_test in range(tests_n):
          [n, k] = _read_ints()
          result = find_nearest_beautiful_number(lower_bound=n, k_parameter=k)
          print(result)
  
  
  def find_nearest_beautiful_number(lower_bound: int, k_parameter: int):
      # k = 3;
      # 54648262 -> 54649444
      # 54649444 -> 54654444
      # or maybe
      # 54648262 -> 54649
      # 54649 -> 5465
      # or maybe
      # 54648262 -> 54648263 -> ... -> 5464827 -> ...
      
      x = lower_bound
      while True:
          while x % 10 == 0:
              x //= 10
          if _is_beautiful(x, k_parameter):
              break
          else:
              x += 1
      
      zeros_n = 0
      while x < lower_bound:
          x *= 10
          zeros_n += 1
      if zeros_n > 0:
          zeros_n -= 1
          x //= 10
      
      for zeros_delta in _itertools.count():
          curr_x = x * 10**zeros_delta
          curr_zeros_n = zeros_n + zeros_delta
          tail = int('1'*curr_zeros_n) if curr_zeros_n else 0
          for filler_digit in range(10):
              candidate = curr_x + tail*filler_digit
              if candidate >= lower_bound and _is_beautiful(candidate, k_parameter):
                  return candidate
  
  
  def _is_beautiful(x: int, k_parameter: int):
      assert x >= 1
      return len(set(str(x))) <= k_parameter
  
  
  def _read_ints():
      return map(int, _read_string().split())
  
  
  def _read_string():
      result = _sys.stdin.readline()
      assert result and result[-1] == '\n'
      return result[:-1]
  
  
  if __name__ == '__main__':
      _main()
  