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 time
  import random
  
  DEB = False
  
  def slow_solve(n, k):
  	min_k_beautiful = n
  	while len(set(str(min_k_beautiful))) > k:
  		min_k_beautiful += 1
  	return min_k_beautiful
  
  def dig_to_num(digits):
  	return int(''.join(map(str, digits)))
  
  def num_to_dig(num):
  	return [int(dig) for dig in str(num)]
  	
  def solve(n, k):
  	i = 0
  	digits = num_to_dig(n)
  	chosen_digits = []
  
  	def debug_print():
  		if not DEB:
  			return
  		print('\n\tn = {}\n\ti = {}\n\tk-beautiful = {}\n\tchosen = {}'.format(dig_to_num(digits), i, dig_to_num(digits), chosen_digits))
  
  	while i < len(digits):
  		debug_print()
  
  		dig = digits[i]
  
  		if len(chosen_digits) < k and dig not in chosen_digits:
  			chosen_digits.append(dig)
  			i += 1
  			continue
  
  		if dig in chosen_digits:
  			digits[i] = dig
  			i += 1
  
  		else:
  			if dig > max(chosen_digits):
  					i -= 1
  
  			if chosen_digits[-1] not in digits[:i]:
  				chosen_digits[-1] += 1
  				if chosen_digits.count(chosen_digits[-1]) > 1:
  					chosen_digits.pop(-1)
  
  			digits = digits[:i] + [digits[i] + 1] + [min(chosen_digits) if len(chosen_digits) != k - 1 else 0] * (len(digits) - i - 1)
  
  	debug_print()
  
  	return dig_to_num(digits)
  
  
  def solve_tests(tests):
  	return [solve(n, k) for n, k in tests]
  
  
  def print_sol(sol):
  	[print(min_num) for min_num in sol]
  
  
  def print_test(t, tests):
  	print()
  	print(t)
  	[print(test[0], test[1]) for test in tests]
  	print()
  
  def parse_input():
  	t = int(input())
  	tests = [(list(map(int, input().split()))) for _ in range(t)]
  	return t, tests
  
  def checker(t, tests):
  	for test in tests:
  		my_sol = solve_tests([test])[0]
  		true_sol = slow_solve(test[0], test[1])
  		print(test[0], my_sol, true_sol)
  		assert my_sol == true_sol
  
  
  def main():
  	t, tests = parse_input()
  
  	# t = 10 ** 3
  	# tests = [(random.randint(10 ** 4, 10 ** 5), random.randint(1,11)) for _ in range(1, t)]
  	# tests = [(random.randint(9 * 10 ** 8 + 10 ** 7, 10 ** 9), 2) for _ in range(1, t)]
  
  	# t = 1
  	# tests = [[102,1]]
  
  	# if DEB: print_test(t, tests)
  	# s = time.time()
  	# solve_tests(tests)
  	print_sol(solve_tests(tests))
  	# print(time.time() - s)
  	# if DEB: print(slow_solve(tests[0][0], tests[0][1]))
  
  	# checker(t, tests)
  
  if __name__ == "__main__":
  	main()
  