It is a complicated version of problem F1. The difference between them is the constraints (F1: $k \le 2$, F2: $k \le 10$).

You are given an integer $n$. Find the minimum integer $x$ such that $x \ge 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 \le t \le 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 \le n \le 10^9$, $1 \le k \le 10$).


-----Output-----

For each test case output on a separate line $x$ — the minimum $k$-beautiful integer such that $x \ge n$.


-----Examples-----

Input
6
2021 3
177890 2
34512 3
724533 4
998244353 1
12345678 10
Output
2021
181111
34533
724542
999999999
12345678


-----Note-----

None

Difficulty: HARD
Tags: Bit manipulation

Graph traversal

Constructive algorithms

Complete search

Greedy algorithms

Dynamic programming
Skill types: Dynamic programming

Bit manipulation

Complete search

Greedy algorithms

Starter code:

Solutions:
from sys import stdin, stdout

def find_next_big(d, dic):
	for i in range(d + 1, 10):
		if dic[i] > 0:
			return i
	return -1

def find_min(dic):
	for i in range(0, 10):
		if dic[i] > 0:
			return i
	return -1

def find_cnt(dic):
	cnt = 0
	for i in range(0, 10):
		if dic[i] > 0:
			cnt += 1
	return cnt

def solve(n, k):
	dic = {}
	for i in range(10):
		dic[i] = 0
	sn = str(n)
	ck = 0
	for i in range(len(sn)):
		d = ord(sn[i]) - ord('0')
		if dic[d] == 0:
			if ck == k:
				nb = find_next_big(d, dic)
				if nb >= 0:
					cm = find_min(dic)
					res = sn[:i] + str(nb) + str(cm) * (len(sn) - i - 1)
					return res
				else:
					j = i - 1
					tv = -1
					while dic[ord(sn[j]) - ord('0')] != 1:
						tv = find_next_big(ord(sn[j]) - ord('0'), dic)
						if tv != -1:
							break
						dic[ord(sn[j]) - ord('0')] -= 1
						j -= 1
					pv = ord(sn[j]) - ord('0')
					if tv == -1:
						tv = pv + 1
					dic[tv] += 1
					dic[pv] -= 1
					if find_cnt(dic) < k:
						res = sn[:j] + str(tv) + '0' * (len(sn) - j - 1)
					else:
						cm = find_min(dic)
						res = sn[:j] + str(tv) + str(cm) * (len(sn) - j - 1)
					return res
			ck += 1
		dic[d] += 1
	return sn
t = int(stdin.readline())
for _ in range(t):
	(n, k) = map(int, stdin.readline().split())
	r = solve(n, k)
	stdout.write(r + '\n')


import sys
t = int(input())
for i in range(t):
	(n, k) = sys.stdin.readline().split()
	n = n.lstrip('000000000')
	k = int(k)
	L = []
	for s in n:
		if int(s) not in L:
			L.append(int(s))
	if len(L) <= k:
		print(n)
	else:
		L = L[:k]
		Num = list(map(int, n))
		ind = Num.index(L[-1])
		maxL = max(L)
		bada = False
		i = 0
		while i < len(n):
			if bada:
				Num[i] = 0
			elif Num[i] > maxL:
				bada = True
				while Num[i] + 1 > maxL and i > ind:
					i -= 1
				Num[i] += 1
				if i == ind:
					L[-1] += 1
					if L[-1] in L[:-1]:
						L[-1] = 0
			elif Num[i] not in L:
				bada = True
			i += 1
		L.sort()
		Go = dict()
		ind = 0
		for i in range(L[-1] + 1):
			while i > L[ind]:
				ind += 1
			Go[i] = str(L[ind])
		minL = str(L[0])
		bada = False
		for i in range(len(Num)):
			if bada == True:
				Num[i] = minL
			else:
				if Num[i] not in L:
					bada = True
				Num[i] = Go[Num[i]]
		print(int(''.join(Num)))


import sys
n = ''
k = l = 0
d = [0] * 9

def dfs(cur, dset):
	p = len(cur)
	if p == l:
		return cur
	if cur > n:
		nd = 0
	else:
		nd = int(n[p])
	for i in range(nd, 10):
		if i in dset:
			r = dfs(cur + str(i), dset)
			if r != -1:
				return r
		elif len(dset) < k:
			r = dfs(cur + str(i), dset | set([i]))
			if r != -1:
				return r
	return -1
for _ in range(int(sys.stdin.readline())):
	(n, k) = sys.stdin.readline().split()
	k = int(k)
	l = len(n)
	sys.stdout.write(dfs('', set()) + '\n')


t = int(input())
while t:
	(num, k) = [int(tok) for tok in input().split()]
	ans = 111111111111111
	num = str(num)
	n = len(num)
	s = set()
	for ch in num:
		s.add(ch)
	if len(s) <= k:
		print(int(num))
	else:
		for ind in range(0, n):
			if num[ind] == '9':
				continue
			done = set()
			for i in range(0, ind):
				done.add(num[i])
			if len(done) > k:
				continue
			elif len(done) == k:
				to_fill = None
				mi = '9'
				for el in done:
					mi = min(mi, el)
					if el > num[ind]:
						if to_fill is None:
							to_fill = el
						else:
							to_fill = min(to_fill, el)
				if to_fill is not None:
					ans = min(ans, int(num[:ind] + to_fill + mi * (n - ind - 1)))
			else:
				mi = '9'
				for i in range(0, 9):
					if str(i) > num[ind]:
						mi = str(i)
						break
				done.add(mi)
				if len(done) == k:
					ans = min(ans, int(num[:ind] + mi + min(done) * (n - ind - 1)))
				else:
					ans = min(ans, int(num[:ind] + mi + '0' * (n - ind - 1)))
		print(ans)
	t -= 1


from collections import Counter

def solve(n, k, cur, cur_set):
	if len(cur) > len(str(n)) or len(cur_set) > k or cur < str(n)[:len(cur)]:
		return None
	if len(cur) == len(str(n)) and cur >= str(n):
		return cur
	for i in range(10):
		if i not in cur_set:
			cur_set.add(i)
			ans = solve(n, k, cur + str(i), cur_set)
			cur_set ^= {i}
		else:
			ans = solve(n, k, cur + str(i), cur_set)
		if ans != None:
			return ans
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(solve(n, k, '', set()))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	tmp = n
	while len(set(str(tmp))) > k:
		if tmp % 10 == 0:
			tmp //= 10
		else:
			tmp += 1
	if len(set(str(tmp))) < k:
		print(str(tmp) + '0' * (len(str(n)) - len(str(tmp))))
	else:
		print(str(tmp) + min(str(tmp)) * (len(str(n)) - len(str(tmp))))


import os, sys
from io import BytesIO, IOBase

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class dict(dict):

	def __missing__(self, key):
		return 0
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda dtype: dtype(input().strip())
inp_d = lambda dtype: [dtype(x) for x in input().split()]
inp_2d = lambda dtype, n: [inp(dtype) for _ in range(n)]
inp_2ds = lambda dtype, n: [inp_d(dtype) for _ in range(n)]
inp_enu = lambda dtype: [(i, x) for (i, x) in enumerate(inp_d(dtype))]
inp_enus = lambda dtype, n: [[i] + [inp_d(dtype)] for i in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b
get_bit = lambda x, i: x >> i & 1
for _ in range(inp(int)):
	(n, k) = inp_d(int)
	n1 = str(n)
	(ans, ln) = (float('inf'), len(n1))
	digs = set()
	for i in n1:
		if len(digs) == k - 1:
			break
		digs.add(i)
	digs = list(digs)
	for i in range(10):
		(cur, lst, flag) = ([], -1, 0)
		if str(i) not in digs:
			digs.append(str(i))
			flag = 1
		digs.sort()
		for j in n1:
			for dig in digs[:-1]:
				if j <= dig:
					cur.append(dig)
					if j < dig:
						cur.extend([digs[0]] * (ln - len(cur)))
					lst = len(cur) - 1
					break
			else:
				if j <= digs[-1]:
					cur.append(digs[-1])
					if j < digs[-1]:
						cur.extend([digs[0]] * (ln - len(cur)))
						break
				elif lst == -1:
					cur = ['9'] * 10
					break
				else:
					cur = cur[:lst + 1]
					for dig in digs:
						if cur[lst] < dig:
							cur[lst] = dig
							break
					cur.extend([digs[0]] * (ln - len(cur)))
					break
			if len(cur) == len(n1):
				break
		if flag:
			digs.remove(str(i))
		ans = min(ans, int(''.join(cur)))
	print(ans)


def number(L):
	r = 0
	for d in L:
		r = r * 10 + int(d)
	return r

def go(n, i, D, eq):
	if i == len(n):
		return (True, [])
	if eq:
		for d in D:
			if n[i] == d:
				(flag, x) = go(n, i + 1, D, True)
				if flag:
					return (True, [d] + x)
			if n[i] < d:
				(flag, x) = go(n, i + 1, D, False)
				if flag:
					return (True, [d] + x)
		return (False, [])
	else:
		(flag, x) = go(n, i + 1, D, False)
		return (True, [D[0]] + x)

def find(n, k):
	if len(set(n)) == 1:
		return n
	D = []
	for d in map(int, n):
		if d not in D:
			D.append(d)
	if len(D) <= k:
		return n
	U = [D[:k]]
	E = D[:k]
	if E[-1] + 1 in E:
		E[-1] = 0
	else:
		E[-1] = (E[-1] + 1) % 10
	U.append(E)
	r = 10 ** 20
	for digits in U:
		x = []
		digits.sort()
		(flag, x) = go(list(map(int, n)), 0, digits, True)
		if flag:
			r = min(r, number(x))
	return r
T = int(input())
for _ in range(T):
	(n, k) = input().split(' ')
	k = int(k)
	print(find(n, k))


import sys
import time
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = list(map(int, input().split()))
		digits = len(str(n))
		first = str(n)[0]
		if digits == 1:
			print(n)
			continue
		if k == 1:
			if int(first * digits) >= n:
				print(first * digits)
			else:
				print(str(int(first) + 1) * digits)
			continue
		m = str(n)
		picked = [first]
		picked_list = [i == int(first) for i in range(10)]
		left = k - 1
		res = ''
		big = 0
		maxx = int(first)
		for i in range(digits):
			if big:
				if left == 1:
					res += (digits - i) * '0'
				else:
					res += (digits - i) * str(min([int(j) for j in picked]))
				break
			if left == 0:
				minpicked = str(min([int(j) for j in picked if int(j) >= int(m[i])]))
				if int(minpicked) > int(m[i]):
					res += minpicked
					big = 1
					continue
				if int(res + m[i] + str(maxx) * (digits - i - 1)) >= n:
					res += minpicked
					continue
				else:
					res += str(sorted([int(j) for j in picked if int(j) >= int(m[i])])[1])
					big = 1
					continue
			if picked_list[int(m[i])]:
				res += m[i]
				continue
			if left >= 2:
				maxx = max(int(m[i]), maxx)
				picked.append(m[i])
				picked_list[int(m[i])] = True
				left -= 1
				res += m[i]
				continue
			if left == 1:
				if int(res + m[i] + str(max(maxx, int(m[i]))) * (digits - i - 1)) >= n:
					maxx = max(int(m[i]), maxx)
					picked.append(m[i])
					picked_list[int(m[i])] = True
					left = 0
					res += m[i]
					continue
				else:
					big = 1
					if picked_list[int(m[i]) + 1]:
						res += str(int(m[i]) + 1)
					else:
						left -= 1
						picked.append(str(int(m[i]) + 1))
						picked_list[int(m[i]) + 1] = True
						maxx = max(int(m[i]) + 1, maxx)
						res += str(int(m[i]) + 1)
					continue
		print(res)
main()


def int_(l):
	return int(''.join((str(kk) for kk in l)))

def f(n, k):
	if k == 1:
		fdig = n[0]
		ff = int_([fdig] * len(n))
		nn = int_(n)
		if ff >= nn:
			return ff
		else:
			return int_([fdig + 1] * len(n))
	digs = set()
	ii = -1
	for i in range(len(n)):
		if len(digs) == k and n[i] not in digs:
			ii = i
			break
		digs.add(n[i])
	if ii == -1:
		return int_(n)
	dg = n[ii]
	for ddd in range(dg + 1, 10):
		if ddd in digs:
			ans = n[:ii] + [ddd] + [min(digs)] * (len(n) - ii - 1)
			return int_(ans)
	nw = n[:ii - 1] + [n[ii - 1] + 1] + [0] * (len(n) - ii)
	return f(nw, k)
for _ in range(int(input())):
	(n_, b) = input().split()
	k = int(b)
	n = [int(ii) for ii in n_]
	print(f(n, k))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	x = n
	while len(set(str(x))) > k:
		x = x // 10 if x % 10 == 0 else x + 1
	p = str(x)
	d = '0' if len(set(p)) < k else min(p)
	print(p + d * (len(str(n)) - len(p)))


import sys
input = sys.stdin.readline
from functools import lru_cache
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(n)
	m = len(s)
	p = [0] * 12
	p[0] = 1
	for i in range(1, 12):
		p[i] = 10 * p[i - 1]

	@lru_cache(None)
	def dp(i, tight, mask):
		if i == m:
			return 0
		ans = float('inf')
		for j in range(10):
			mask2 = mask | 1 << j
			if bin(mask2).count('1') > k:
				continue
			if tight and j < int(s[i]):
				continue
			tight2 = tight and j == int(s[i])
			cur = p[m - 1 - i] * j + dp(i + 1, tight2, mask2)
			if cur < ans:
				ans = cur
				break
		return ans
	ans = dp(0, 1, 0)
	print(ans)


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07

def dfs(a, b, p, c):
	if a == b:
		return c
	for (i, j) in adj[a]:
		if i == p:
			continue
		temp = dfs(i, b, a, c + j)
		if dfs(i, b, a):
			mx = max(i, mx)
			return 1
	return tot
ans = 0
dig = {}
s = 0
k = 0

def recur_dp(i, tight):
	global s, ans, k, dig
	if i == len(s):
		return ans
	t = 0
	for j in range(10):
		if tight and j < int(s[i]):
			continue
		if t >= 2:
			continue
		if len(dig) == k and dig.get(j) is None:
			continue
		ans *= 10
		ans += j
		abe = 0
		if dig.get(j) is None:
			abe = 1
		dig[j] = 1
		fl = recur_dp(i + 1, tight & (j == int(s[i])))
		if fl != -1:
			return fl
		if abe:
			del dig[j]
		ans //= 10
	return -1

def hnbhai(tc):
	global s, n, k, ans, dig
	(n, k) = sd()
	s = str(n)
	ans = 0
	dig = {}
	print(recur_dp(0, 1))
for _ in range(sb()):
	hnbhai(_ + 1)


import math

def diff_digits(x):
	a = [0] * 10
	n = x
	while 1:
		if n == 0:
			break
		else:
			a[n % 10] += 1
			n = n // 10
	count = 0
	for i in a:
		if i > 0:
			count += 1
	return [count, a]

def check(string, k, n):
	temp = ''
	for i in string:
		temp = temp + str(i)
	if diff_digits(int(temp))[0] <= k:
		return True
	else:
		return False

def print_output(t_arr):
	temps = ''
	for klp in t_arr:
		temps = temps + str(klp)
	return temps

def strong(n_arr, t_arr, k, n, digits, i, flag):
	if i >= digits:
		return True
	pl = int(n_arr[i])
	if flag:
		for j in range(0, 10):
			t_arr[i] = j
			if check(t_arr[0:i + 1], k, n):
				if strong(n_arr, t_arr, k, n, digits, i + 1, flag):
					return print_output(t_arr)
	else:
		for j in range(pl, 10):
			t_arr[i] = j
			if check(t_arr[0:i + 1], k, n):
				if strong(n_arr, t_arr, k, n, digits, i + 1, flag):
					return print_output(t_arr)
			flag = True
	return False

def solver(t):
	n = int(t[0])
	k = int(t[1])
	get = diff_digits(n)
	if get[0] <= k:
		return n
	digits = int(math.log(n, 10)) + 1
	n_str = t[0]
	t_arr = [0] * digits
	return strong(n_str, t_arr, k, n, digits, 0, False)
t = int(input())
z = [None] * t
for i in range(t):
	z[i] = input().split(' ')
for i in range(t):
	print(solver(z[i]))


import sys
from sys import stdin

def solve(n, k):
	s = set()
	ans = []
	for i in range(len(n)):
		dig = n[i]
		if len(s) == k and dig not in s:
			bigmin = None
			for c in s:
				if dig < c:
					if bigmin == None:
						bigmin = c
					else:
						bigmin = min(bigmin, c)
			if bigmin == None:
				divser = 10 ** (len(n) - i)
				nex = (int(n) // divser + 1) * divser
				return solve(str(nex), k)
			else:
				ans.append(bigmin)
				allmin = min(s)
				while len(ans) < len(n):
					ans.append(allmin)
				return ''.join(ans)
		s.add(dig)
		ans.append(dig)
	return ''.join(ans)
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	(n, k) = stdin.readline()[:-1].split()
	k = int(k)
	ANS.append(solve(n, k))
print('\n'.join(ANS))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def input_list():
	return list(map(int, input().split()))

def input_string():
	s = input()
	return list(s[:len(s) - 1])

def input_int_gen():
	return map(int, input().split())

def largest(using, n_digits):
	return (10 ** n_digits - 1) // 9 * max(using)

def smallest(using, n_digits, zero_allowed=False):
	if zero_allowed:
		return 0
	return (10 ** n_digits - 1) // 9 * min(using)

def lowest_greater_single(using, n):
	return min([x for x in using if x > n], default=-1)

def lowest_greater(using, mini, n_digits):
	highest = mini // 10 ** (n_digits - 1)
	rem = mini % 10 ** (n_digits - 1)
	if n_digits == 1:
		return mini if mini in using else lowest_greater_single(using, mini)
	if highest in using:
		if rem > largest(using, n_digits - 1):
			if lowest_greater_single(using, highest) == -1:
				return -1
			return lowest_greater_single(using, highest) * 10 ** (n_digits - 1) + smallest(using, n_digits - 1)
		else:
			return highest * 10 ** (n_digits - 1) + lowest_greater(using, rem, n_digits - 1)
	else:
		if lowest_greater_single(using, highest) == -1:
			return -1
		return lowest_greater_single(using, highest) * 10 ** (n_digits - 1) + smallest(using, n_digits - 1)

def nbn(mini, using, n_digits, k):
	if n_digits == 1:
		if mini in using or k > len(using):
			return mini
		return lowest_greater_single(using, mini)
	if len(using) == k:
		return lowest_greater(using, mini, n_digits)
	else:
		highest = mini // 10 ** (n_digits - 1)
		rem = mini % 10 ** (n_digits - 1)
		if highest in using:
			res = nbn(rem, using, n_digits - 1, k)
			return highest * 10 ** (n_digits - 1) + res
		else:
			res = nbn(rem, using | {highest}, n_digits - 1, k)
			if res != -1:
				return highest * 10 ** (n_digits - 1) + res
			else:
				return (highest + 1) * 10 ** (n_digits - 1) + smallest(using | {highest + 1}, n_digits - 1, len(using | {highest + 1}) < k)
tests = inp()
for _ in range(tests):
	(n, k) = input_int_gen()
	print(nbn(n, set(), len(str(n)), k))


from collections import Counter

def solve():
	(n, k) = input().split()
	k = int(k)
	cnt = Counter(n)
	if len(cnt) <= k:
		print(n)
		return
	cnt = Counter()
	ans = []
	for c in n:
		if c in cnt:
			cnt[c] += 1
			ans.append(c)
			continue
		if len(cnt) == k:
			break
		cnt[c] += 1
		ans.append(c)
	i = len(ans)
	for j in range(int(n[i]) + 1, 10):
		if str(j) in cnt:
			ans.append(str(j))
			m = min(cnt.keys())
			while len(ans) < len(n):
				ans.append(m)
			print(''.join(ans))
			return
	while i >= 0:
		i -= 1
		c = ans[i]
		cnt[c] -= 1
		if cnt[c] == 0:
			del cnt[c]
		for nxt in range(int(c) + 1, 10):
			nxt = str(nxt)
			if nxt not in cnt:
				if len(cnt) == k:
					continue
			cnt[nxt] += 1
			ans[i] = nxt
			if len(cnt) < k:
				cnt['0'] += 1
			m = min(cnt.keys())
			for j in range(i + 1, len(ans)):
				ans[j] = m
			while len(ans) < len(n):
				ans.append(m)
			print(''.join(ans))
			return
	assert 1 < 0
for _ in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	(n, k) = map(int, input().split())
	S = str(n)
	x = ''
	ANS = int(str(min(9, int(S[0]) + 1)) * len(S))
	for i in range(len(S)):
		x += S[i]
		if len(set(x)) > k:
			break
		if i == len(S) - 1:
			ANS = n
		if i != len(S) - 1:
			j = S[i + 1]
			for t in sorted(x):
				if t > j:
					break
			if t > j:
				y = x + t
				if len(set(y)) == k:
					u = min(y)
				else:
					u = '0'
				ANS = min(ANS, int(y + u * (len(S) - len(y))))
		if i != len(S) - 1:
			j = S[i + 1]
			if j == '9':
				continue
			y = x + str(int(j) + 1)
			if len(set(y)) > k:
				continue
			if len(set(y)) == k:
				u = min(y)
			else:
				u = '0'
			ANS = min(ANS, int(y + u * (len(S) - len(y))))
	print(ANS)


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = [i for i in str(n)]
	l = len(arr)
	if len(set(arr)) <= k:
		print(n)
		continue
	ans = -1
	for i in range(0, l):
		s = set()
		vals = []
		for j in arr[:i]:
			s.add(j)
			vals.append(j)
		p = len(s)
		if p > k or arr[i] == '9':
			continue
		if p < k:
			vals.append(str(int(arr[i]) + 1))
			s.add(str(int(arr[i]) + 1))
		else:
			mi = float('inf')
			for j in s:
				if int(j) > int(arr[i]):
					mi = min(mi, int(j))
			if mi == float('inf'):
				continue
			vals.append(str(mi))
		mi = 0
		p = len(s)
		if p == k:
			mi = float('inf')
			for j in s:
				mi = min(mi, int(j))
		mi = str(mi)
		for j in arr[i + 1:]:
			vals.append(str(mi))
		ans = ''.join(vals)
	try:
		ans = int(ans)
		print(ans)
	except:
		print(n, k, ans)


times = int(input())
for _ in range(times):
	(n, k) = map(int, input().split())
	num = n
	while len(set(str(num))) > k:
		if num % 10 == 0:
			num = num // 10
		else:
			num += 1
	last = str(min(str(num))) * (len(str(n)) - len(str(num)))
	print(str(num) + last)


from collections import defaultdict
from collections import deque
from sys import stdout

def get_digits(n):
	digits = deque()
	while n > 0:
		digits.appendleft(n % 10)
		n //= 10
	return digits

def get_tail(s, k, n):
	avail_digits = 10 - len(s)

def get_number(digits, left_unchanged, k):
	s = set()
	for i in range(left_unchanged):
		s.add(digits[i])
	if len(digits) == left_unchanged:
		if len(s) <= k:
			return int(''.join([str(i) for i in digits]))
		else:
			return -1
	if len(s) > k:
		return -1
	for i in range(digits[left_unchanged] + 1, 10):
		remove = i not in s
		s.add(i)
		j = 0
		d = deque()
		while j < 10 and len(s) + len(d) < k:
			d.append(j)
		if len(s) + len(d) != k or left_unchanged + 1 + len(d) > len(digits):
			if remove:
				s.remove(i)
			continue
		min_s_d = None
		for s_i in s:
			if min_s_d is None or min_s_d > s_i:
				min_s_d = s_i
		for d_i in d:
			if min_s_d is None or min_s_d > d_i:
				min_s_d = d_i
		while left_unchanged + 1 + len(d) < len(digits):
			d.appendleft(min_s_d)
		d2 = []
		for j in range(left_unchanged):
			d2.append(digits[j])
		d2.append(i)
		d2 += d
		return int(''.join([str(i) for i in d2]))
	return -1

def get_min_number(digits_count, k):
	digits_count = max(digits_count, k)
	digits = deque(range(2, k))
	while len(digits) < digits_count - 1:
		digits.appendleft(0)
	digits.appendleft(1)
	return ''.join([str(i) for i in digits])
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	digits = get_digits(n)
	for i in range(len(digits), -1, -1):
		ans = get_number(digits, i, k)
		if ans >= n:
			break
	if ans < n:
		ans = get_min_number(len(digits) + 1, k)
	print(ans)


import os, sys
from io import BytesIO, IOBase
from collections import Counter

def comp(arr1, arr2):
	if len(arr1) > len(arr2):
		return 1
	if len(arr1) < len(arr2):
		return 0
	for (i, j) in zip(arr1, arr2):
		if i > j:
			return 1
		if i < j:
			return 0

def main():
	for _ in range(int(input())):
		(n, k) = input().split()
		k = int(k)
		n = list(map(int, n))
		if len(Counter(n)) <= k:
			print(''.join(map(str, n)))
			continue
		le = len(n)
		ans = [1] + [0] * le if k >= 2 else [1] * (le + 1)
		curr = []
		mini = float('inf')
		uni = Counter()
		for (idx, i) in enumerate(n):
			if len(uni) > k:
				break
			for j in range(i + 1, 10):
				uni[j] += 1
				if len(uni) < k:
					poss = curr + [j] + [0] * (le - idx - 1)
					if comp(ans, poss):
						ans = poss
				elif len(uni) == k:
					mini1 = min(mini, j)
					poss = curr + [j] + [mini1] * (le - idx - 1)
					if comp(ans, poss):
						ans = poss
				uni[j] -= 1
				if not uni[j]:
					del uni[j]
			mini = min(mini, i)
			curr += [i]
			uni[i] += 1
		print(''.join(map(str, ans)))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def find_nearest(s, k):
	ln = len(s)
	if max(s[:ln - 1]) > s[ln - 1]:
		x = list(set(s[:ln - 1]))
		x.sort()
		for it in x:
			if it > s[-1]:
				s = s[:ln - 1] + it
				return s
	else:
		for i in range(ln - 1, -1, -1):
			x = s[:i]
			while x[-1] < '9':
				x = str(int(x) + 1)
				if len(set(x)) <= k:
					if len(set(x)) == k:
						x = x + (ln - len(x)) * min(set(x))
						return x
					else:
						x = x + (ln - len(x)) * '0'
						return x

def solve(s, k):
	if len(set(str(s))) <= k:
		return s
	s = str(s)
	for i in range(len(s)):
		if len(set(s[:i + 1])) > k:
			break
	i += 1
	x = s[:i]
	x = find_nearest(x, k)
	ans = x + (len(s) - i) * min(set(x))
	return ans
n = int(input())
for _ in range(n):
	(s, k) = [int(i) for i in input().split()]
	print(solve(s, k))


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):
	prefix = lower_bound
	while not _is_beautiful(prefix, k_parameter):
		if prefix % 10 == 0:
			prefix //= 10
		else:
			prefix += 1
	zeros_n = len(str(lower_bound)) - len(str(prefix))
	tail_digit = '0' if _measure_k(prefix) < k_parameter else min(str(prefix))
	tail = int(tail_digit * zeros_n) if zeros_n > 0 else 0
	return prefix * 10 ** zeros_n + tail

def _is_beautiful(x: int, k_parameter: int):
	return _measure_k(x) <= k_parameter

def _measure_k(x: int):
	assert x >= 1
	return len(set(str(x)))

def _read_ints():
	return map(int, _sys.stdin.readline().split())
_main()


for nt in range(int(input())):
	(n, k) = map(int, input().split())
	m = n
	while len(set(str(n))) > k:
		if n % 10 == 0:
			n = n // 10
		else:
			n += 1
	end = str(min(str(n))) * (len(str(m)) - len(str(n)))
	print(int(str(n) + end))


t = int(input())
some_list = []
for i in range(t):
	some_list.append(input())
for i in range(t):
	n_k = some_list[i].split()
	n = int(n_k[0])
	k = int(n_k[1])
	x = n
	while len(set(str(n))) > k:
		if n % 10 == 0:
			n = n // 10
		else:
			n += 1
	end = str(min(str(n))) * (len(str(x)) - len(str(n)))
	print(int(str(n) + end))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve():
	(n, k) = map(int, input().split())
	x = n
	m = len(str(x))
	while len(set(str(x))) > k:
		if x % 10 == 0:
			x //= 10
		else:
			x += 1
	suff = '0' if len(set(str(x))) < k else min(set(str(x)))
	ans = str(x) + suff * (m - len(str(x)))
	print(ans)
for nt in range(int(input())):
	solve()


T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	s = str(n)
	if k == 1:
		t = s[0] * len(s)
		if t >= s:
			print(t)
		else:
			t = chr(ord(s[0]) + 1) * len(s)
			print(t)
	else:
		(cur, cnt) = (s[0], 0)
		ans = ''
		ans += s[0]
		isUsed = [False for _ in range(10)]
		isUsed[ord(s[0]) - ord('0')] = True
		mx = ord(s[0]) - ord('0')
		for i in range(1, len(s)):
			x = ord(s[i]) - ord('0')
			if s[i] == s[i - 1]:
				ans += s[i]
			else:
				if not isUsed[x]:
					k -= 1
				if k == 1:
					break
				else:
					ans += s[i]
					isUsed[x] = True
					mx = max(mx, x)
		cnt = len(ans)
		for i in range(len(s) - cnt):
			for d in range(10):
				t = ans + chr(d + ord('0')) + chr(max(d, mx) + ord('0')) * (len(s) - cnt - i - 1)
				if not isUsed[d] and k == 1 and (t >= s):
					ans += chr(d + ord('0'))
					isUsed[d] = True
					mx = max(mx, d)
					k -= 1
					break
				elif isUsed[d] and t >= s:
					ans += chr(d + ord('0'))
					break
		print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def solve(n, k):
	ans = int('9' * 10) - n
	x = [int(p) for p in str(n)]
	if len(set(x)) <= k:
		return n
	if k == 1:
		for i in '123456789':
			y = int(i * len(x))
			if y >= n:
				ans = min(ans, y - n)
		return n + ans
	chosen = [False] * 10
	i = 0
	while k != 1:
		if not chosen[x[i]]:
			chosen[x[i]] = True
			k -= 1
		i += 1
	unch = [k for k in range(10) if not chosen[k]]
	chosen = [k for k in range(10) if chosen[k]]
	for num in unch:
		digits = sorted(chosen + [num])
		mx = digits[0]
		b = [x[0]]
		for i in range(1, len(x)):
			b += [x[i]]
			last = b[-1] not in digits
			if b[-1] > digits[-1]:
				break
			if x[i] != digits[-1]:
				for d in digits:
					if d > x[i]:
						b[-1] = d
						break
				while len(b) != len(x):
					b += [digits[0]]
				y = int(''.join((str(k) for k in b)))
				if y >= n:
					ans = min(ans, y - n)
				while len(b) != i:
					b.pop()
				b += [x[i]]
			if last:
				break
	return n + ans
for _ in range(int(input()) if True else 1):
	(n, k) = map(int, input().split())
	print(solve(n, k))


import sys

def main(N, K):
	S = str(N)
	d = len(S)
	if d <= K:
		return N
	if len(set(S)) <= K:
		return N
	for i in range(d - 1, -1, -1):
		up = set(S[:i])
		if len(up) > K:
			continue
		if len(up) == K:
			n = int(S[i])
			for m in sorted(up):
				if int(m) > n:
					break
			else:
				continue
			res = S[:i] + m
			mn = min(up)
			for _ in range(i + 1, d):
				res += mn
			return int(res)
		n = int(S[i])
		if n == 9:
			continue
		m = str(n + 1)
		res = S[:i] + m
		up.add(m)
		if len(up) == K:
			mn = min(up)
			for _ in range(i + 1, d):
				res += mn
			return int(res)
		for _ in range(i + 1, d):
			res += '0'
		return int(res)
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	print(main(N, K))


import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
from math import cos, sin
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	d = dict()
	a = [int(i) for i in str(n)]
	for i in range(len(a)):
		if a[i] not in d:
			if len(d) == k:
				break
		d[a[i]] = d.get(a[i], 0) + 1
	if i == len(a) - 1 and a[i] in d:
		print(n)
		continue
	ans = float('inf')
	while i >= 0:
		if a[i] in d:
			d[a[i]] -= 1
			if d[a[i]] == 0:
				d.__delitem__(a[i])
		if len(d) == k:
			if a[i] + 1 in d:
				x = a[:i] + [a[i] + 1]
				t = min(d)
				for _ in range(len(x), len(a)):
					x.append(t)
				x = int(''.join(map(str, x)))
				if x >= n:
					ans = min(ans, x)
			else:
				t = float('inf')
				for k1 in sorted(d):
					if k1 > a[i]:
						t = min(t, k1)
				if t != float('inf'):
					x = a[:i] + [t]
					t = min(d)
					for _ in range(len(x), len(a)):
						x.append(t)
					x = int(''.join(map(str, x)))
					if x >= n:
						ans = min(ans, x)
		elif len(d) == k - 1:
			if a[i] + 1 in d:
				x = a[:i] + [a[i] + 1]
				t = 0
				for _ in range(len(x), len(a)):
					x.append(t)
				x = int(''.join(map(str, x)))
				if x >= n:
					ans = min(ans, x)
			else:
				x = a[:i] + [a[i] + 1]
				if d:
					t = min(d)
				else:
					t = a[i] + 1
				t = min(t, a[i] + 1)
				for _ in range(len(x), len(a)):
					x.append(t)
				x = int(''.join(map(str, x)))
				if x >= n:
					ans = min(ans, x)
		else:
			x = a[:i] + [a[i] + 1]
			t = 0
			for _ in range(len(x), len(a)):
				x.append(t)
			x = int(''.join(map(str, x)))
			if x >= n:
				ans = min(ans, x)
		i -= 1
	print(ans)


def lower_bound(nums, x):
	for i in range(len(nums)):
		if nums[i] >= x:
			return i
	return -1

def check(n, k, num, pos, _n, wid):
	x = num
	nums = dict()
	while x > 0:
		nums.setdefault(x % 10, 0)
		x //= 10
	nums = list(nums.keys())
	nums.sort()
	flag = 0
	for i in range(pos, wid):
		tmp = int(_n[i])
		x = lower_bound(nums, tmp) if flag == 0 else 0
		if x == -1:
			return -1
		if flag == 0 and nums[x] > tmp:
			flag = 1
		num = num * 10 + nums[x]
	return num

def work(n, k):
	res = 10 ** 11
	_n = str(n)
	wid = len(_n)
	vis = dict()
	tmp = 0
	cnt = 0
	for i in range(wid):
		num = int(_n[i])
		vis.setdefault(num, 0)
		if vis[num] == 1:
			tmp = tmp * 10 + num
			continue
		if cnt == k:
			res = check(n, k, tmp, i, _n, wid)
			if res == -1:
				return work((tmp + 1) * 10 ** (wid - i), k)
			return res
		cnt += 1
		vis[num] = 1
		tmp = tmp * 10 + num
	return tmp
_t = int(input())
for _c in range(_t):
	(n, k) = map(int, input().split())
	print(work(n, k))


def solve(n, k):
	a = sorted(((n.index(x), int(x)) for x in set(n)))
	if len(a) <= k:
		return n
	d = {x[1] for x in a[:k]}
	for i in range(a[k][1], 10):
		if i in d:
			m = n[:a[k][0]] + str(i)
			break
	else:
		m = solve(str(int(n[:a[k][0]]) + 1), k)
	return m + (min(m) if len(set(m)) == k else '0') * (len(n) - len(m))
for _ in range(int(input())):
	(n, k) = input().split()
	print(solve(n, int(k)))


def solve():
	(n, k) = map(int, input().split())
	s = str(n)
	se = set()
	for i in range(len(s)):
		se.add(s[i])
	if len(se) <= k:
		return s
	se = set()
	i = 0
	while True:
		se.add(s[i])
		if len(se) > k:
			break
		i += 1
	se.remove(s[i])
	arr = sorted(se)
	while True:
		cur = set((c for c in s[:i]))
		if len(cur) == k:
			if s[i] >= arr[-1]:
				i -= 1
				continue
			j = 0
			while arr[j] <= s[i]:
				j += 1
			return s[:i] + arr[j] + arr[0] * (len(s) - i - 1)
		c = str(int(s[i]) + 1)
		cur.add(c)
		r = min(cur) if len(cur) == k else '0'
		return s[:i] + c + r * (len(s) - i - 1)
import sys
input = lambda : sys.stdin.readline().rstrip()
t = int(input())
for i in range(t):
	print(solve())


import sys
import copy
INF = 10 ** 10

def digs(n):
	ans = []
	while n > 0:
		ans.append(n % 10)
		n //= 10
	return list(reversed(ans))

def find_ans(n, k):
	n_digs = digs(n)
	if k == 1:
		base = (10 ** len(n_digs) - 1) // 9
		for d in range(1, 10):
			if d * base >= n:
				return d * base
		print('ANS NOT FOUND')
		sys.exit(1)
	ans = INF
	nums_found = set()
	bad = False
	prefix = 0
	for (i, d) in enumerate(n_digs):
		realLen = i
		next_dig = d + 1
		while len(nums_found) + int(next_dig not in nums_found) > k:
			next_dig += 1
			if next_dig > 9:
				break
		if next_dig <= 9:
			new_prefix = prefix * 10 + next_dig
			test_ans = new_prefix * 10 ** (len(n_digs) - i - 1)
			new_nums_found = copy.deepcopy(nums_found)
			new_nums_found.add(next_dig)
			if len(new_nums_found) == k:
				test_ans += min(new_nums_found) * (10 ** (len(n_digs) - i - 1) - 1) // 9
			ans = min(test_ans, ans)
		prefix *= 10
		prefix += d
		nums_found.add(d)
	if len(nums_found) <= k:
		return n
	return ans
nums = (int(tok) for tok in sys.stdin.read().split())
T = next(nums)
for _ in range(T):
	n = next(nums)
	k = next(nums)
	print(find_ans(n, k))


for i in range(int(input())):
	(n, k, x, tt) = map(int, input().split() * 2)
	while len(set(str(x))) > k:
		x = x // 10 if not x % 10 else x + 1
	print(str(x) + ('0' if len(set(str(x))) < k else min(str(x))) * (len(str(n)) - len(str(x))))


def upList(s, i):
	left = s[:i]
	right = s[i:]
	left = list(str(int(''.join(left)) + 1))
	return left + right

def jg(x, val):
	y = set((i for i in x if i >= val))
	if len(y) == 0:
		return None
	return min(y)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(str(n))
	i = len(s) - 1
	while i >= 0:
		cMax = set()
		j = 0
		while len(cMax) < k and j < len(s):
			cMax.add(s[j])
			j += 1
		if j == len(s):
			break
		if s[i] not in cMax:
			z = jg(cMax, s[i])
			if z == None:
				s = upList(s, i)
				for var in range(i, len(s)):
					s[var] = '0'
				i = len(s) - 1
			else:
				s[i] = z
				for var in range(i + 1, len(s)):
					s[var] = min(cMax)
				i -= 1
		else:
			i -= 1
	print(''.join(s))


l = len
(_, *t) = open(0)
for p in t:
	(x, k) = p.split()
	k = int(k)
	n = x
	while l(set(x)) > k:
		x = str(int(x) + 1).strip('0')
	print(x + (l(n) - l(x)) * min(x + '0' * (l(set(x)) < k)))


def f(n, k):
	dig_set = set()
	pre = ''
	for x in n:
		dig_set.add(x)
		if len(dig_set) > int(k):
			post_head = x
			dig_set.remove(x)
			break
		pre += x
		post_head = ''
	post = n[len(pre):]
	if post_head:
		min_dig = min(dig_set)
		poss_digs = {i for i in dig_set if i > x}
		if poss_digs:
			min_poss_dig = min(poss_digs)
			ans = pre + min_poss_dig + min_dig * (len(post) - 1)
		else:
			pre = str(int(pre) + 1)
			if len(set(pre)) == int(k):
				ans = pre + min(set(pre)) * len(post)
			elif len(set(pre)) < int(k):
				ans = pre + '0' * len(post)
			else:
				ans = f(pre + '0' * len(post), k)
	else:
		ans = pre
	return ans
for i in range(int(input())):
	(n, k) = input().split()
	print(f(n, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(n)
	if k == 1:
		if int(s[0] * len(s)) >= n:
			print(s[0] * len(s))
		else:
			print(str(int(s[0]) + 1) * len(s))
		continue
	(dg, prob) = (set(), False)
	for (i, v) in enumerate(s):
		if v not in dg:
			if len(dg) < k:
				dg.add(v)
			else:
				prob = i
				break
	if not prob:
		print(n)
	else:
		(res, g) = (s[prob:], max(dg))
		if int(str(g) * len(res)) >= int(res):
			ans = s[:prob]
			for i in range(prob, len(s)):
				if s[i] in dg:
					ans += s[i]
				else:
					ans += min((d for d in dg if d > s[i]))
					omp = len(s) - len(ans)
					ans += min(dg) * omp
					break
			print(ans)
		else:
			for i in range(prob - 1, -1, -1):
				if s[i] < g:
					prob = i
					break
			if s[prob] in s[:prob]:
				ans = s[:prob]
				ans += min((d for d in dg if d > s[prob]))
				omp = len(s) - len(ans)
				ans += min(dg) * omp
			else:
				dg.remove(s[prob])
				ans = s[:prob]
				nou = str(int(s[prob]) + 1)
				ans += nou
				if nou in dg:
					dg.add('0')
				omp = len(s) - len(ans)
				ans += min(dg) * omp
			(dg, k) = (set(), k - 1)
			for (i, v) in enumerate(s):
				if v not in dg:
					if len(dg) < k:
						dg.add(v)
					else:
						prob = i
						break
			ans2 = s[:prob]
			nou = str(int(s[prob]) + 1)
			ans2 += nou
			dg.add(nou)
			omp = len(s) - len(ans2)
			ans2 += min(dg) * omp
			print(min(ans, ans2))


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):
	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]
_main()


import sys

def get_digits(n):
	digits = []
	while n != 0:
		digits.append(n % 10)
		n = n // 10
	return digits[::-1]

def construct(digits):
	result = 0
	power = 1
	for d in digits[::-1]:
		result += power * d
		power *= 10
	return result

def solve(n, k):
	digits = get_digits(n)
	if len(set(digits)) <= k:
		return n
	met = [False for _ in range(10)]
	counter = 0
	for (i, d) in enumerate(digits):
		if met[d] == True:
			continue
		if counter == k:
			break
		met[d] = True
		counter += 1
	for t in range(digits[i] + 1, 10):
		if met[t] == True:
			answer = digits[:i] + [t] + [min(digits[:i])] * (len(digits) - i - 1)
			return construct(answer)
	prefix = construct(digits[:i])
	sub_answer = get_digits(solve(prefix + 1, k))
	sub_k = len(set(sub_answer))
	if sub_k < k:
		filler = 0
	else:
		filler = min(sub_answer)
	answer = sub_answer + [filler] * (len(digits) - len(sub_answer))
	return construct(answer)

def main():
	outputs = []
	fin = sys.stdin
	N = int(fin.readline())
	for _ in range(N):
		(n, k) = map(int, fin.readline().split())
		outputs.append(solve(n, k))
	print('\n'.join(map(str, outputs)))
main()


from math import floor, log

def upper_bound(s, n):
	mn = ':'
	for x in s:
		if x > n and x < mn:
			mn = x
	return max(s) if mn == ':' else mn
for input_number in range(int(input())):
	(n, k) = map(int, input().split())
	while True:
		s = str(n)
		d = set(s[0])
		for i in range(1, len(s)):
			if s[i] not in d:
				if len(d) == k:
					if s[i] >= upper_bound(d, s[i]):
						n += (10 - int(s[i])) * 10 ** (len(s) - i - 1)
					else:
						n += (int(upper_bound(d, s[i])) - int(s[i])) * 10 ** (len(s) - i - 1)
					n -= int('0' if s[i + 1:] == '' else s[i + 1:])
					break
				else:
					d.add(s[i])
		else:
			break
	print(n)


for s in [*open(0)][1:]:
	(prefix, k) = map(int, s.split())
	n = str(prefix)
	while len(set(str(prefix))) > k:
		prefix = prefix // 10 if not prefix % 10 else prefix + 1
	prefix = str(prefix)
	x = len(n) - len(prefix)
	suffix = str(min(prefix) * x)
	print(prefix + suffix)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	d = [int(x) for x in str(n)]
	l = len(d)
	if n == 1000000000:
		print(1111111111 if k == 1 else 1000000000)
		continue
	if k >= len(set(d)):
		print(n)
		continue
	mn = 10 ** 15
	for i in range(l):
		for v in range(d[i] + 1, 10):
			uniq = set(d[:i]) | {v}
			if len(uniq) > k:
				continue
			elif len(uniq) < k:
				uniq |= {0}
			nd = d[:i] + [v] + [min(uniq)] * (l - i - 1)
			nn = int(''.join(map(str, nd)))
			if nn < mn:
				mn = nn
	print(mn)


import sys
input = sys.stdin.readline
bits = [[] for _ in range(11)]
for bit in range(1 << 10):
	se = set()
	for i in range(10):
		if bit >> i & 1:
			se.add(i)
	bits[len(se)].append(se)

def main():
	(n, k) = input().strip().split()
	k = int(k)
	l = len(n)
	times = (10 ** l - 1) // 9
	min_ = 10 ** 20
	N = int(n)
	se_ = set()
	ans_ = []
	for s in n:
		if len(se_) >= k - 2:
			break
		s = int(s)
		se_.add(s)
		ans_.append(s)
	if len(ans_) == l:
		print(n)
		return
	n = n[len(ans_):]
	l = len(n)
	for se2 in bits[min(k, 2)]:
		se = se2 | se_
		if max(se) * times < N:
			continue
		tmp = -1
		nex = [-1] * 10
		for i in range(9, -1, -1):
			if i in se:
				tmp = i
			nex[i] = tmp
		ans = ans_.copy()
		flg = False
		for i in range(l):
			if flg:
				ans.append(nex[0])
				continue
			s = int(n[i])
			t = nex[s]
			if t == s:
				ans.append(s)
			elif t != -1:
				ans.append(t)
				flg = True
			else:
				cnt = 1
				while 1:
					s = ans[-1]
					ans.pop()
					if nex[s + 1] != -1:
						ans.append(nex[s + 1])
						break
					cnt += 1
				for _ in range(cnt):
					ans.append(nex[0])
				flg = True
		min_ = min(min_, int(''.join(map(str, ans))))
	print(min_)
for _ in range(int(input())):
	main()


import itertools
from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 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))

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 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()
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.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


def naiveSolve(n, k):
	i = n
	while True:
		i2 = i
		u = set()
		while i2 > 0:
			u.add(i2 % 10)
			i2 //= 10
		if len(u) <= k:
			return i
		i += 1
	return

def solve(n, k):
	narr = []
	n2 = n
	while n2 > 0:
		narr.append(n2 % 10)
		n2 //= 10
	narr.reverse()
	ansarr = []
	unique = set()
	stoppingIndex = -1
	for (i, x) in enumerate(narr):
		if x in unique or len(unique) + 1 <= k:
			ansarr.append(x)
			unique.add(x)
		else:
			stoppingIndex = i
			break
	if stoppingIndex != -1:
		seen = sorted(unique)
		if narr[stoppingIndex] < max(seen):
			for x in seen:
				if x > narr[stoppingIndex]:
					ansarr.append(x)
					break
			while len(ansarr) < len(narr):
				ansarr.append(min(seen))
		else:
			i = stoppingIndex - 1
			while True:
				ansarr[i] += 1
				if ansarr[i] == 10:
					ansarr.pop()
					i -= 1
					continue
				if len(set(ansarr)) <= k:
					break
			unique = set(ansarr)
			if len(unique) == k - 1:
				remaining = 0
			else:
				remaining = min(unique)
			while len(ansarr) < len(narr):
				ansarr.append(remaining)
	ans = 0
	for x in ansarr:
		ans *= 10
		ans += x
	return ans

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		(n, k) = readIntArr()
		ans = solve(n, k)
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 998244353
from math import gcd, floor, ceil
for _abc in range(1):
	main()


from sys import stdin
import heapq
from collections import deque
from bisect import bisect_left
DIGITS = [str(i) for i in range(10)]

def solve():
	(str_n, k) = stdin.readline().split()
	n = int(str_n)
	k = int(k)
	L = len(str_n)
	best = '9' * L
	for i in range(9):
		foo = str(i) * L
		if foo >= str_n:
			best = min(best, foo)
	if k == '1' or n < 10:
		print(best)
		return
	remaining = k
	ans = []
	used = {str(i): 0 for i in range(10)}
	idx = 0
	ignore = False
	while idx < L:
		digit = str_n[idx]
		if ignore:
			if remaining > 0:
				ans.append('0')
				used['0'] += 1
			else:
				minimum = '9'
				for x in DIGITS:
					if used[x] > 0:
						minimum = min(minimum, x)
				ans.append(minimum)
		elif used[digit]:
			ans.append(digit)
			used[digit] += 1
		elif remaining >= 1:
			used[digit] = 1
			remaining -= 1
			ans.append(digit)
		else:
			flag = True
			for i in used.keys():
				if used[i] and digit < i:
					flag = False
					ignore = True
					ans.append(i)
					break
			if flag:
				while ans:
					curr = ans.pop(-1)
					idx -= 1
					used[curr] -= 1
					if used[curr] == 0:
						ignore = True
						foo = str(int(curr) + 1)
						ans.append(foo)
						used[foo] += 1
						if used[foo] > 1:
							remaining += 1
						break
					for j in DIGITS:
						if used[j] and j > curr:
							ans.append(j)
							used[j] += 1
							ignore = True
							break
					if ignore:
						break
		idx += 1
	print(''.join(ans))
t = int(stdin.readline().strip())
for _ in range(t):
	solve()


def naiveSolve():
	return

def solve(n, k):
	narr = []
	n2 = n
	while n2 > 0:
		narr.append(n2 % 10)
		n2 //= 10
	narr.reverse()
	ansarr = narr.copy()
	while len(set(ansarr)) > k:
		ansarr[-1] += 1
		while ansarr[-1] == 10:
			ansarr.pop()
			ansarr[-1] += 1
	if len(set(ansarr)) < k:
		append = 0
	else:
		append = min(ansarr)
	while len(ansarr) < len(narr):
		ansarr.append(append)
	ans = 0
	for x in ansarr:
		ans *= 10
		ans += x
	return ans

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		(n, k) = readIntArr()
		ans = solve(n, k)
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 998244353
from math import gcd, floor, ceil
for _abc in range(1):
	main()


def _measure_k(x):
	return len(set(str(x)))
tests_n = int(input())
for i_test in range(tests_n):
	(n, k) = map(int, input().split())
	prefix = n
	while _measure_k(prefix) > k:
		if prefix % 10 == 0:
			prefix //= 10
		else:
			prefix += 1
	prefix = str(prefix)
	tail_digit = '0' if _measure_k(prefix) < k else min(prefix)
	tail = tail_digit * (len(str(n)) - len(prefix))
	print(prefix + tail)


def first_bad(A, k):
	seen = [0] * 10
	for (i, a) in enumerate(A):
		if seen[a] == 0:
			k -= 1
			seen[a] = 1
		if k < 0:
			return i
	return -1
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	A = [ord(c) - ord('0') for c in str(n)]
	while True:
		i = first_bad(A, k)
		if i == -1:
			break
		A[i] += 1
		while i and A[i] == 10:
			i -= 1
			A[i] += 1
		for j in range(i + 1, len(A)):
			A[j] = 0
	print(''.join((str(x) for x in A)))


def main(t):
	(n, k) = map(int, input().split())
	s = str(n)
	m = len(s)
	dic = {}
	ans = ''
	for i in range(m):
		if s[i] in dic:
			dic[s[i]] += 1
		else:
			dic[s[i]] = 1
		if len(dic) == k and i < m - 1:
			if s[i + 1:] > max(dic) * (m - i - 1):
				dic[s[i]] -= 1
				if dic[s[i]] == 0:
					del dic[s[i]]
				if str(int(s[i]) + 1) in dic and len(dic) < k:
					ans += str(int(s[i]) + 1)
					ans += '0' * (m - i - 1)
				else:
					dic[str(int(s[i]) + 1)] = 1
					ans += str(int(s[i]) + 1)
					ans += min(dic) * (m - i - 1)
				break
			else:
				ans += s[i]
				broken = i + 1
				flag = True
				for j in range(i + 1, m):
					if s[j] < max(dic):
						broken = j
					if s[j] not in dic:
						flag = False
						break
				if flag:
					broken = m
				ans += s[i + 1:broken]
				if broken == m:
					break
				for d in range(int(s[broken]) + 1, 10):
					if str(d) in dic:
						break
				dic[str(d)] = 1
				ans += str(d)
				ans += min(dic) * (m - len(ans))
				break
		ans += s[i]
	print(ans)
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


def getBeautiful(num, k):
	if len(set(str(num))) <= k:
		return num
	unstableIdx = k
	st = str(num)
	digits = set(map(int, set(st[:unstableIdx])))
	while int(st[unstableIdx]) in digits or len(digits) < k:
		if unstableIdx != len(st) - 1:
			digits.add(int(st[unstableIdx]))
			unstableIdx += 1
		else:
			return num
	n = int(st[unstableIdx])
	while n not in digits:
		n += 1
		if n == 10:
			break
	if n in digits:
		return int(st[:unstableIdx] + str(n) + str(min(digits)) * (len(st) - unstableIdx - 1))
	else:
		return getBeautiful((int(st[:unstableIdx]) + 1) * 10 ** (len(st) - unstableIdx), k)
for t in range(int(input())):
	(n, k) = map(int, input().split())
	print(getBeautiful(n, k))


import bisect
import copy
import decimal
import fractions
import functools
import heapq
import itertools
import math
import random
import sys
from collections import Counter, deque, defaultdict
from functools import lru_cache, reduce
from heapq import heappush, heappop, heapify, heappushpop, _heappop_max, _heapify_max

def _heappush_max(heap, item):
	heap.append(item)
	heapq._siftdown_max(heap, 0, len(heap) - 1)

def _heappushpop_max(heap, item):
	if heap and item < heap[0]:
		(item, heap[0]) = (heap[0], item)
		heapq._siftup_max(heap, 0)
	return item
from math import degrees, gcd as GCD
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
T = int(readline())
for _ in range(T):
	(N, K) = map(int, readline().split())
	S = str(N)
	l = len(S)
	ans = ''
	se = set()
	m = -1
	for digit in range(l):
		for i in range(0, 10):
			if digit == 0 and i == 0:
				continue
			if int(S[:digit + 1]) > int(ans + str(i)):
				continue
			if len(se) + (not i in se) < K:
				ans += str(i)
				se.add(i)
				m = max(m, i)
				break
			elif len(se) + (not i in se) > K:
				continue
			elif N <= int(ans + str(i) + str(max(m, i)) * (l - digit - 1)):
				ans += str(i)
				se.add(i)
				m = max(m, i)
				break
	print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def findnext(c, dic):
	for d in range(int(c) + 1, 10):
		if str(d) in dic:
			return str(d)

def nextdigit(c):
	return str(int(c) + 1)

def main(t):
	(n, k) = map(int, input().split())
	s = list(str(n))
	m = len(s)
	dic = {}
	for c in s:
		if c not in dic:
			dic[c] = 0
		dic[c] += 1
	if len(dic) <= k:
		print(''.join(s))
		return
	while len(dic) > k:
		dic[s[-1]] -= 1
		if dic[s[-1]] == 0:
			del dic[s[-1]]
		while s[-1] == '9':
			s.pop()
			dic[s[-1]] -= 1
			if dic[s[-1]] == 0:
				del dic[s[-1]]
		s[-1] = str(int(s[-1]) + 1)
		if s[-1] not in dic:
			dic[s[-1]] = 0
		dic[s[-1]] += 1
	if len(dic) < k:
		ans = ''.join(s) + '0' * (m - len(s))
	else:
		ans = ''.join(s) + min(dic) * (m - len(s))
	print(ans)
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	sn = [int(i) for i in str(n)]
	s = set()
	ans = []
	for i in sn:
		if i in s:
			ans.append(i)
		elif len(s) < k:
			s.add(i)
			ans.append(i)
		else:
			flag = 0
			for j in range(1, 10):
				if i + j in s:
					ans.append(i + j)
					flag = 1
					break
			if flag:
				ans.extend([min(ans)] * (len(sn) - len(ans)))
			else:
				while len(ans):
					if ans.count(ans[-1]) == 1:
						s.remove(ans[-1])
						s.add(ans[-1] + 1)
						ans.append(ans.pop() + 1)
						break
					else:
						flag1 = 0
						for j in range(1, 10):
							if ans[-1] + j in s:
								flag1 = ans[-1] + j
								break
						if flag1:
							ans.pop()
							ans.append(flag1)
							break
						else:
							ans.pop()
				if len(s) == k:
					ans.extend([min(ans)] * (len(sn) - len(ans)))
				else:
					ans.extend([0] * (len(sn) - len(ans)))
			break
	for i in ans:
		print(i, end='')
	print()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class RangeQuery:

	def __init__(self, data, func=min):
		self.func = func
		self._data = _data = [list(data)]
		(i, n) = (1, len(_data[0]))
		while 2 * i <= n:
			prev = _data[-1]
			_data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
			i <<= 1

	def query(self, start, stop):
		depth = (stop - start).bit_length() - 1
		return self.func(self._data[depth][start], self._data[depth][stop - (1 << depth)])

	def __getitem__(self, idx):
		return self._data[0][idx]

def check(st, n, k):
	for i in range(n - k + 1):
		g = st.query(i, i + k)
		if g > 1:
			return True
	return False
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict, deque
from math import ceil, floor, sqrt, log2, gcd, pi
from heapq import heappush, heappop
from fractions import Fraction
from bisect import bisect_left, bisect, bisect_right
from itertools import combinations_with_replacement, permutations
import sys
abc = 'abcdefghijklmnopqrstuvwxyz'
ABC = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in str(n)]
	s = set()
	l = len(arr)
	pre = 0
	for _ in range(1000):
		pre = 0
		arr = [int(i) for i in str(n)]
		s = set()
		l = len(arr)
		le = 0
		for i in arr:
			if i in s:
				le += 1
				pre = pre * 10 + i
			elif len(s) < k:
				s.add(i)
				le += 1
				pre = pre * 10 + i
			else:
				pre = pre * 10 + i
				pre += 1
				lp = len(str(pre))
				pre = pre * 10 ** (l - lp)
				n = pre
				break
		if le == l:
			print(pre)
			break


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
		print(res)
main()


import sys, io, os
input = sys.stdin.readline
inf = float('inf')
mod = 10 ** 9 + 7

def yn(a):
	print('YES' if a else 'NO')
ceil = lambda a, b: (a + b - 1) // b
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def ahead():
	s = set()
	for i in range(nlen):
		s.add(n[i])
		if len(s) > k:
			return i
	return -1
t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = [ord(i) - ord('0') for i in n]
	nlen = len(n)
	k = int(k)
	while 1:
		indexa = ahead()
		if indexa == -1:
			print(*n, sep='')
			break
		while n[indexa] == 9:
			indexa -= 1
		n[indexa] += 1
		for j in range(indexa + 1, nlen):
			n[j] = 0


for _ in range(int(input())):
	(x, k) = input().split()
	k = int(k)
	n = len(x)
	while len(set(x)) > k:
		x = str(int(x) + 1).rstrip('0')
	print(x + (min(x) if len(set(x)) == k else '0') * (n - len(x)))


for _ in range(int(input())):
	(n, k) = input().split()
	k = int(k)
	m = len(n)
	d = {}
	i = 0
	for i in range(m):
		if n[i] not in d:
			if len(d) == k:
				break
			d[n[i]] = 0
		d[n[i]] += 1
	else:
		print(n)
		continue
	n = list(n)
	while True:
		if n[i] == '9' or (len(d) == k and max(d) <= n[i]):
			i -= 1
			d[n[i]] -= 1
			if d[n[i]] == 0:
				del d[n[i]]
		else:
			if len(d) < k:
				n[i] = str(int(n[i]) + 1)
				if n[i] not in d:
					d[n[i]] = 0
				d[n[i]] += 1
				p = '0' if len(d) < k else min(d)
				for i in range(i + 1, m):
					n[i] = p
			else:
				n[i] = min((j for j in d if j > n[i]))
				for i in range(i + 1, m):
					n[i] = min(d)
			break
	print(''.join(n))


import sys
from bisect import bisect_right as lb
from collections import deque
from queue import PriorityQueue as pq
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
dig = {}
ans = 0
s = ''
k = 0

def dp(i, t):
	global dig, s, k, ans
	if i == len(s):
		return ans
	tot = 0
	for j in range(10):
		if t and j < int(s[i]):
			continue
		if tot >= 2:
			continue
		if len(dig) == k and (not dig.get(j)):
			continue
		ans *= 10
		ans += j
		flag = dig.get(j, 0)
		if not flag:
			dig[j] = 1
		temp = dp(i + 1, t and j == int(s[i]))
		if temp != -1:
			return temp
		if not flag:
			del dig[j]
		ans //= 10
	return -1
for _ in range(ii()):
	(n, k) = il()
	s = str(n)
	ans = 0
	dig = {}
	print(dp(0, 1))


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 have_greater_in_lili_or_sel(digit):
			break
		if digit in [d for d in lili if lili[d]]:
			continue
		if digit > sel:
			sel = str(int(sel) + 1)
			if lili[sel]:
				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:
			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]
			maybe_a_better_resut = 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) + n[curr_index:]
				return clean(n, lili)
			for _ in range(len(n) - curr_index):
				maybe_a_better_resut += min_dig
			break
		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)
	print(result)


for i in range(int(input())):
	(a, k) = input().split()
	k = int(k)
	k0 = k
	b = [0] * 10
	a = [int(i) for i in a]
	j = 0
	m = 9
	mx = 0
	for i in a:
		if b[i] == 0:
			k -= 1
		if k < 0:
			break
		j += 1
		b[i] += 1
		m = min(m, i)
		mx = max(mx, i)
	if j == len(a):
		print(*a, sep='')
		continue
	for i in range(a[j] + 1, 10):
		if b[i]:
			a[j] = i
			for k in range(j + 1, len(a)):
				a[k] = m
			break
	else:
		b1 = [0] * 10
		j1 = j
		for i in range(j1):
			if b1[a[i]] == 0 or a[i] != mx:
				j = i + 1
				b1[a[i]] = 1
		if b[a[j - 1]] == 1 or a[j - 1] == mx:
			a[j - 1] += 1
		else:
			while b[a[j - 1] + 1] == 0:
				a[j - 1] += 1
			a[j - 1] += 1
		b = [0] * 10
		for i in range(j):
			b[a[i]] += 1
		if 10 - b.count(0) < k0:
			for i in range(j, len(a)):
				a[i] = 0
		else:
			m = 9
			for i in range(10):
				if b[i]:
					m = min(m, i)
			for i in range(j, len(a)):
				a[i] = m
	print(*a, sep='')


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()
	print_sol(solve_tests(tests))
main()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = input()[:-1].split()
	k = int(k)
	ni = int(n)
	t = ''
	ans = 10 ** 18
	for i in range(len(n)):
		for j in range(1, 10):
			c = len(set(t + str(int(n[i]) + j)))
			if c > k:
				continue
			elif c == k:
				d = ord(min(t + str(int(n[i]) + j))) - ord('0')
				x = int(t + str(int(n[i]) + j))
				while ni > x:
					x *= 10
					x += d
				if ans > x:
					ans = x
			else:
				x = int(t + str(int(n[i]) + j))
				while ni > x:
					x *= 10
				if ans > x:
					ans = x
		t += n[i]
	if len(set(n)) <= k:
		ans = ni
	print(ans)


for _ in range(int(input())):
	(n, k) = input().split()
	k = int(k)
	a = []
	ans = 0
	it = False
	for i in range(len(n)):
		if it:
			if k:
				ans = ans * 10
			else:
				ans = ans * 10 + min(a)
			continue
		j = i
		while j < len(n):
			if n[j] > n[i]:
				j += 1
				break
			j += 1
		j -= 1
		kk = j
		while kk < len(n):
			if n[kk] < n[j]:
				kk += 1
				break
			kk += 1
		kk -= 1
		if n[i] == max(n[i:]) or k > 1 or (k > 0 and int(n[i]) in a) or (a and max(a) >= int(max(n[j:kk + 1]))) or (i == len(n) - 1) or (a and min([int(n[x]) for x in range(i + 1, j + 1)]) < max(a)) or (min([int(n[x]) for x in range(i + 1, j + 1)]) < int(n[i])):
			d = int(n[i])
		else:
			d = int(n[i]) + 1
		if d not in a and k:
			k -= 1
			a.append(d)
			a.sort()
			ans = ans * 10 + d
		else:
			for x in a:
				if x >= d:
					ans = ans * 10 + x
					break
		if ans % 10 > int(n[i]):
			it = True
	print(ans)


import sys
import os
import math
from io import BytesIO, IOBase
from collections import defaultdict, Counter, deque
import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for i in range(t):
	(n, k) = input().split()
	k = int(k)
	n1 = list(map(int, n))
	s1 = set()
	l = len(n1)
	ans = []
	for j in range(l):
		if n1[j] in s1:
			ans.append(n1[j])
		elif len(s1) < k:
			s1.add(n1[j])
			ans.append(n1[j])
		else:
			ma = 10
			for kk in s1:
				if kk > n1[j]:
					ma = min(ma, kk)
			if ma != 10:
				ans.append(ma)
				ans.extend([min(s1)] * (l - len(ans)))
			break
	if len(ans) == l:
		ans = ''.join(map(str, ans))
		print(ans)
	else:
		if k == 1:
			print(str(ans[0] + 1) * l)
			continue
		final = sorted(s1)
		l1 = len(final)
		ans1 = 10 ** 10
		for j in range(1, len(ans)):
			s = set(ans[:j])
			mi = min(s)
			if len(s) == k:
				ind = bisect.bisect_right(final, ans[j])
				if ind != l1:
					cur = ans[:j] + [final[ind]]
				else:
					cur = []
					for kk in range(j + 1):
						if ans[kk] == final[-1]:
							cur.append(ans[kk] + 1)
						else:
							cur.append(ans[kk])
				cur.extend([mi] * (l - j - 1))
			else:
				cur = ans[:j] + [ans[j] + 1]
				s.add(ans[j] + 1)
				if len(s) == k:
					cur.extend([min(s)] * (l - j - 1))
				else:
					cur.extend([0] * (l - j - 1))
			ans1 = min(ans1, int(''.join(map(str, cur))))
		print(ans1)


import sys
input = sys.stdin.readline
tests = int(input())
for test in range(tests):
	(tInt, k) = map(int, input().split())
	t = [int(x) for x in str(tInt)]
	foundInts = 0
	ints = []
	firstOccurence = {}
	pos = 0
	while pos < len(t):
		char = t[pos]
		if char not in ints:
			if foundInts < k:
				ints.append(char)
				ints.sort()
				firstOccurence[char] = pos
				foundInts += 1
			else:
				break
		pos += 1
	if pos == len(t):
		print(''.join((str(x) for x in t)))
	else:
		fixed = False
		largerThanPos = list(filter(lambda val: val > t[pos], ints))
		if largerThanPos:
			t[pos] = largerThanPos[0]
			fixed = True
		while not fixed:
			pos -= 1
			largerThanPos = list(filter(lambda val: val > t[pos], ints))
			if firstOccurence[t[pos]] == pos:
				ints.remove(t[pos])
				if t[pos] + 1 in ints:
					ints.append(0)
				else:
					ints.append(t[pos] + 1)
				t[pos] = t[pos] + 1
				fixed = True
			elif largerThanPos:
				t[pos] = largerThanPos[0]
				fixed = True
		ints.sort()
		pos += 1
		while pos < len(t):
			t[pos] = ints[0]
			pos += 1
		print(''.join((str(x) for x in t)))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve(n, k, cur, cur_set):
	if len(cur) > len(str(n)) or len(cur_set) > k or cur < str(n)[:len(cur)]:
		return None
	if len(cur) == len(str(n)) and cur >= str(n):
		return cur
	for i in range(10):
		if i not in cur_set:
			cur_set.add(i)
			ans = solve(n, k, cur + str(i), cur_set)
			cur_set ^= {i}
		else:
			ans = solve(n, k, cur + str(i), cur_set)
		if ans != None:
			return ans
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(solve(n, k, '', set()))


def brute(n, k):
	for i in range(int(n), 10 ** len(n)):
		if len(set(str(i))) <= k:
			return i

def strange(n, k):
	if len(set(n)) <= k:
		return int(n)
	str_n = n
	n = list(map(int, list(n)))
	minn = float('inf')
	for i in range(len(n) - 1, -1, -1):
		rp = len(n) - 1 - i
		if len(set(n[0:i])) > k:
			continue
		if len(set(n[0:i])) == k:
			ll = list(filter(lambda x: x > n[i], n[0:i]))
			if len(ll):
				v1 = int(str_n[0:i] + str(min(ll)) + str(min(n[0:i])) * (len(n) - 1 - i))
				if v1 >= int(str_n) and v1 < minn:
					minn = v1
		elif len(set(n[0:i])) == k - 1:
			v1 = int(str_n[0:i] + str(n[i]) + str(min(n[0:i + 1])) * (len(n) - 1 - i))
			ll = list(filter(lambda x: x > n[i], n[0:i]))
			v2 = None
			if len(ll):
				v2 = int(str_n[0:i] + str(min(ll)) + '0' * (len(n) - 1 - i))
			v3 = int(str_n[0:i] + str(n[i] + 1) + str(min(n[0:i] + [n[i] + 1])) * (len(n) - 1 - i))
			for v in [v1, v2, v3]:
				if not v:
					continue
				if v >= int(str_n) and v < minn:
					minn = v
		else:
			v1 = int(str_n[0:i] + str(n[i]) + str(min(n[0:i + 1])) * (len(n) - 1 - i))
			ll = list(filter(lambda x: x > n[i], n[0:i]))
			v2 = None
			if len(ll):
				v2 = int(str_n[0:i] + str(min(ll)) + '0' * (len(n) - 1 - i))
			v3 = int(str_n[0:i] + str(n[i] + 1) + str(min(n[0:i] + [n[i] + 1])) * (len(n) - 1 - i))
			v4 = int(str_n[0:i] + str(n[i]) + '0' * (len(n) - 1 - i))
			v5 = int(str_n[0:i] + str(n[i] + 1) + '0' * (len(n) - 1 - i))
			for v in [v1, v2, v3, v4, v5]:
				if not v:
					continue
				if v >= int(str_n) and v < minn:
					minn = v
	return minn
t = int(input())
for _ in range(t):
	(n, k) = input().split(' ')
	print(strange(n, int(k)))