human
PYTHON3 solution for "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":



=====
Give me a Python code to find the minimum integer x such that x ≥ n and the number x is k-beautiful?
assistant
#Here is Python code to find the minimum integer x such that x ≥ n and the number x is k-beautiful.
 def find_lsb(mask):
	if mask == 0:
		return -1
	lsb = 0
	while True:
		if mask & (1 << lsb):
			break
		lsb += 1
	return lsb

def solve(n, k):
	mask = 0
	cnt = 0
	for c in n:
		if mask & (1 << int(c)):
			continue
		cnt += 1
		mask |= (1 << int(c))
	if cnt <= k:
		return True
	else:
		return False
	
def main():
	t = int(input())
	for tc in range(t):
		n, k = map(int, input().split())
		n = str(n)
		backup_k = k

		if k == 1:
			res = "1" * (len(n) + 1)
			for i in range(10):
				cur = str(i) * len(n)
				if int(cur) >= int(n):
					res = cur
					break
			print(res)
			continue

		res = "1" + "0" * len(n)
		mask = 0
		cur = ""

		for i in range(len(n)):
			c = int(n[i])

			for j in range(c + 1, 10):
				rem_k = k
				if (mask & (1 << j)) == 0:
					rem_k -= 1
				if rem_k < 0:
					continue

				nmask = mask | (1 << j)
				if rem_k > 0:
					nmask |= (1 << 0)
				temp = cur + str(j)
				temp = temp + str(find_lsb(nmask)) * (len(n) - len(temp))
				if int(temp) >= int(n) and int(temp) <= int(res):
					res = temp

			if mask & (1 << c):
				cur = cur + n[i]
				continue

			if k > 0:
				k -= 1
				mask = mask | (1 << c)
				cur = cur + n[i]
			else:
				for i in range(c + 1, 10):
					if mask & (1 << i):
						cur = cur + str(i)
						cur = cur + str(find_lsb(mask)) * (len(n) - len(cur))
						if int(cur) >= int(n) and int(cur) <= int(res):
							res = cur
						break

		if int(cur) >= int(n) and int(cur) <= int(res):
			res = cur

		# res2 = res
		# cur = int(n)
		# while True:
		# 	if solve(str(cur), backup_k) == True:
		# 		res2 = str(cur)
		# 		break
		# 	cur += 1

		# if res != res2:
		# 	print("ERROR!")
		# 	print(res, res2)
		# 	break
		
		print(res)

if __name__ == "__main__":
	main()