It is a simplified version of problem F2. 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 2$).


-----Output-----

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


-----Examples-----

Input
4
1 1
221 2
177890 2
998244353 1
Output
1
221
181111
999999999


-----Note-----

None

Difficulty: HARD
Tags: Bit manipulation

Graph traversal

Constructive algorithms

Sorting

Greedy algorithms

Complete search
Skill types: Complete search

Bit manipulation

Sorting

Greedy algorithms

Starter code:

Solutions:
from itertools import combinations
from bisect import bisect_left
digits = [i for i in range(10)]

def get_all(length, digits, so_far=0):
	if length == 0:
		return [so_far]
	ret = []
	for d in digits:
		if so_far == 0 and d == 0:
			continue
		ret += get_all(length - 1, digits, so_far * 10 + d)
	return ret
all = []
all_1 = []
for length in range(1, 11):
	all_1 += [int(f'{x}' * length) for x in range(1, 10)]
	for p in combinations(digits, 2):
		p = list(p)
		all += get_all(length, p)
all_1.sort()
all += all_1
all.sort()
for _ in range(int(input())):
	(n, k) = [int(item) for item in input().split()]
	ans = float('inf')
	if k == 1:
		ans = all_1[bisect_left(all_1, n)]
	if k == 2:
		ans = min(ans, all[bisect_left(all, n)])
	print(ans)


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


import sys
input = sys.stdin.readline
from pprint import pprint
INF = 1 << 63
l = list()

def f():
	nn = 10
	ss = set()
	for n in range(nn + 1):
		for a in range(10):
			for b in range(10):
				for pat in range(2 ** n):
					x = 0
					for i in range(n):
						x *= 10
						if pat >> i & 1 == 1:
							x += b
						else:
							x += a
					ss.add(x)
	for x in ss:
		l.append(x)
	l.sort()

def do():
	from bisect import bisect_left
	(n, k) = map(int, input().split())
	s = str(n)
	sl = len(str(n))
	if s.count(s[0]) == sl:
		print(s)
		return
	if k == 1:
		for i in range(1, 10):
			if int(str(i) * sl) >= n:
				print(str(i) * sl)
				return
	ind = bisect_left(l, n)
	print(l[ind])
f()
q = int(input())
for _ in range(q):
	do()


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
for _ in range(ii()):
	(n, k) = il()
	if k == 1:
		x = list(str(n))
		for i in range(1, 10):
			y = str(i) * len(x)
			if int(y) >= n:
				print(y)
				break
	else:
		fl = 0
		x = list(str(n))
		ans1 = []
		for i in range(1, 10):
			for j in range(10):
				ans = []
				t = 1
				if i == j:
					continue
				x1 = min(i, j)
				x2 = max(i, j)
				temp = 1
				y1 = 0
				y2 = 0
				for k in range(len(x)):
					if temp == 0:
						ans.append(str(x1))
						y1 = 1
						continue
					if x1 >= int(x[k]):
						ans.append(str(x1))
						y1 = 1
						if x1 > int(x[k]):
							temp = 0
					elif x2 >= int(x[k]):
						ans.append(str(x2))
						y2 = 1
						if x2 > int(x[k]):
							temp = 0
					else:
						k2 = -1
						for k1 in range(k - 1, -1, -1):
							if ans[k1] == str(x1):
								ans[k1] = str(x2)
								k2 = k1
								break
						if k2 == -1:
							t = 0
							break
						for k1 in range(k2 + 1, k):
							ans[k1] = str(x1)
						ans.append(str(x1))
						temp = 0
				if t and y1 and y2:
					ans1.append(int(''.join(ans)))
		for i in range(1, 10):
			y = str(i) * len(x)
			if int(y) >= n:
				ans1.append(int(y))
		if len(ans1):
			prinT(min(ans1))
		else:
			print('1' + '0' * len(x))


import bisect
(l, c) = ([], '0123456789')
for i in c:
	for j in c:
		z = [i, j]
		for k in z:
			z += [k + i, k + j]
			if len(k) > 10:
				break
		l += z
(l, x, y) = ({*l}, [], [])
for i in l:
	if len({*i}) == 1:
		x += [i]
	else:
		y += [i]
(x, y) = (sorted(map(int, x)), sorted(map(int, y)))
for _ in [*open(0)][1:]:
	(n, k) = map(int, _.split())
	print(n if len({*str(n)}) <= k else x[bisect.bisect(x, n)] if k == 1 else y[bisect.bisect(y, n)])


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


def nr_distinct(n):
	return len(set(list(n)))

def get(n, idx, k):
	if n[idx] == '9':
		return -1
	digs = set(list(n[:idx]))
	if len(digs) > k:
		return -1
	if len(digs) == k:
		x = chr(ord('9') + 1)
		y = x
		for ch in digs:
			if ord(ch) > ord(n[idx]) and ord(ch) < ord(x):
				x = ch
			if ord(ch) < ord(y):
				y = ch
		if ord(x) <= ord('9'):
			return n[:idx] + x + ''.join([y] * (len(n) - idx - 1))
		else:
			return -1
	else:
		x = chr(ord(n[idx]) + 1)
		digs.add(x)
		if len(digs) < k:
			y = '0'
		else:
			y = chr(ord('9') + 1)
			for ch in digs:
				if ord(ch) < ord(y):
					y = ch
		return n[:idx] + x + ''.join([y] * (len(n) - idx - 1))
for _ in range(int(input())):
	(n, k) = input().split()
	k = int(k)
	if nr_distinct(n) <= k:
		print(n)
		continue
	found = False
	for idx in range(len(n) - 1, -1, -1):
		ans = get(n, idx, k)
		if ans != -1:
			print(ans)
			found = True
			break
	if not found:
		print(''.jioin(['1'] * (len(n) + 1)))


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


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
X1 = []
for i in range(1, 10):
	for j in range(1, 11):
		x = str(i) * j
		x = int(x)
		X1.append(x)
import itertools
X2 = []
for i in range(10):
	for j in range(10):
		if i == j:
			continue
		A = [str(i), str(j)]
		for l in range(1, 11):
			for p in itertools.product(A, repeat=l):
				if p[0] == '0':
					continue
				p = list(p)
				p = ''.join(p)
				p = int(p)
				X2.append(p)
X1.sort()
X2.sort()
import bisect
for _ in range(t):
	(n, k) = map(int, input().split())
	if k == 1:
		j = bisect.bisect_left(X1, n)
		print(X1[j])
	else:
		j = bisect.bisect_left(X2, n)
		print(X2[j])


t = int(input())
k1 = [0]
for i in range(1, 10):
	for j in range(1, 11):
		e = str(i) * j
		e = int(e)
		k1.append(e)
k1 = sorted(k1)
k2 = []

def ad(i, j, s):
	if len(s) == 10:
		if s != s[0] * len(s):
			k2.append(int(s))
	else:
		if s != '' and s != s[0] * len(s):
			k2.append(int(s))
		if not (i == '0' and s == ''):
			ad(i, j, s + i)
		ad(i, j, s + j)
for i in range(10):
	for j in range(i + 1, 10):
		ad(str(i), str(j), '')
k2 += k1
k2 = sorted(k2)

def binsearch(l, r, arr, n):
	while l + 1 < r:
		mid = (l + r) // 2
		if arr[mid] <= n:
			l = mid
		else:
			r = mid
	if n == arr[l]:
		return l
	return r
for i in range(t):
	(a, b) = map(int, input().split())
	if b == 1:
		ans = binsearch(-1, len(k1), k1, a)
		print(k1[ans])
	else:
		ans = binsearch(-1, len(k2), k2, a)
		print(k2[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 bisect import *
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def dadd(d, p, val):
	if p in d:
		d[p].append(val)
	else:
		d[p] = [val]

def gi():
	return [xx for xx in input().split()]

def gtc(tc, *ans):
	print('Case #' + str(tc) + ':', *ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def bits(i, n):
	p = bin(i)[2:]
	return (n - len(p)) * '0' + p

def prec(a, pre):
	for i in a:
		pre.append(pre[-1] + i)
	pre.pop(0)

def YN(flag):
	print('YES' if flag else 'NO')

def si():
	return list(input().rstrip())

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

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = fi()
INF = 10 ** 18
uu = t
mod = 10 ** 9 + 7
a = set()
b = set()
for i in range(1, 10):
	for j in range(1, 11):
		b.add(int(str(i) * j))

def rec(i, j, k, l, p=''):
	if k + l == 0:
		a.add(p)
		return
	if k:
		rec(i, j, k - 1, l, p + i)
	if l:
		rec(i, j, k, l - 1, p + j)
for i in range(10):
	for j in range(i + 1, 10):
		for k in range(2, 11):
			for l in range(1, k):
				rec(str(i), str(j), l, k - l)
a = list(a)
b = list(b)
b.sort()
for i in range(len(a)):
	a[i] = int(a[i])
a.sort()
while t > 0:
	t -= 1
	(n, k) = mi()
	if k == 2:
		p = bisect_left(a, n)
		print(a[p])
	else:
		p = bisect_left(b, n)
		print(b[p])


import collections
import bisect
from itertools import combinations
t = int(input())
all_cur = set()
for x in combinations(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'], 2):
	for l in range(1, 10):
		cur = list(range(l))
		for i in range(l + 1):
			for y in combinations(cur, i):
				cur_res = ''
				for j in range(l):
					if j in y:
						cur_res += x[0]
					else:
						cur_res += x[1]
				if cur_res[0] == '0' and cur_res != '0':
					continue
				all_cur.add(int(cur_res))
all_cur = list(all_cur)
all_cur.sort()
for case in range(t):
	(n, k) = list(map(int, input().split()))
	if n == 1000000000:
		if k == 2:
			print(1000000000)
		else:
			print(1111111111)
		continue
	if k == 1:
		cur = []
		for i in range(0, 10):
			cur.append(str(i) * len(str(n)))
		res = float('inf')
		for x in cur:
			if len(str(int(x))) != len(x):
				continue
			if int(x) >= n:
				res = min(res, int(x))
		print(res)
	else:
		index = bisect.bisect_left(all_cur, n)
		print(all_cur[index])


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 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 I():
	return input().strip()

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import copy, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, combinations, groupby
from operator import itemgetter
from itertools import chain, combinations

def greater(num, men, mex):
	res = []
	flag = False
	num = str(num)
	i = 0
	while i < len(str(num)):
		if flag:
			res.append(str(men))
		elif men > int(num[i]):
			res.append(str(men))
			flag = True
		elif men == int(num[i]):
			res.append(str(men))
		elif mex > int(num[i]):
			res.append(str(mex))
			flag = True
		elif mex == int(num[i]):
			res.append(str(mex))
		else:
			while res:
				pop = res.pop()
				i -= 1
				if pop != str(mex):
					res.append(str(mex))
					flag = True
					break
			if not res:
				return False
		i += 1
	return ''.join(res)
for _ in range(II()):
	(inp, k) = LI()
	inp = str(inp)
	if k == 1:
		size = len(inp)
		for i in range(10):
			s = ''.join([str(i) for x in range(size)])
			if int(inp) <= int(s):
				print(int(s))
				break
	else:
		ans = float('inf')
		for i in range(10):
			for j in range(i, 10):
				temp = greater(inp, i, j)
				if temp is not False:
					ans = min(ans, int(temp))
		print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
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')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: math.gcd(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(11)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = n
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			res = mid
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
t = 1
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = str(n)
	st = set()
	l = len(s)
	for i in s:
		st.add(int(i))
		if len(st) > 1:
			break
	if len(set(s)) <= k:
		print(n)
		continue
	st = list(st)
	if st[0] != int(s[0]):
		st = st[::-1]
	m = len(s)
	if k == 1:
		m1 = int(s[0] * m)
		if m1 >= n:
			print(m1)
		else:
			p = str(int(s[0]) + 1)
			print(int(p * m))
	else:
		mn = [int('9' * m)]

		def dfs(a, b, curr, prev, ind):
			if curr >= n:
				mn[0] = min(mn[0], curr)
				return
			if ind == m:
				return
			nx = curr * 10
			m1 = min(a, b)
			m2 = max(a, b)
			if prev:
				dfs(a, b, nx + m1, 1, ind + 1)
			else:
				if int(s[ind]) < m1:
					dfs(a, b, nx + m1, 1, ind + 1)
				elif int(s[ind]) == m1:
					dfs(a, b, nx + m1, 0, ind + 1)
				if int(s[ind]) < m2:
					dfs(a, b, nx + m2, 1, ind + 1)
				elif int(s[ind]) == m2:
					dfs(a, b, nx + m2, 0, ind + 1)
		dfs(st[0], st[1], st[0], 0, 1)
		dfs(st[0], 0, st[0], 0, 1)
		if st[1] != 0:
			dfs(st[0], st[1], st[1], 0, 1)
		if st[1] != 9:
			dfs(st[0], st[1] + 1, st[0], 0, 1)
			dfs(st[0], st[1] + 1, st[1] + 1, 0, 1)
		print(mn[0])


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())
	a = [int(i) for i in str(n)]
	ans = float('inf')
	for i in range(1, 10):
		x = int(str(i) * len(a))
		if x >= n:
			ans = min(ans, x)
	if k == 2:
		for i in range(10):
			for j in range(i + 1, 10):
				ct = []
				bol = True
				for k in range(len(a)):
					if i == 0 and len(ct) == 0:
						if a[k] > j:
							bol = False
							break
						elif a[k] < j:
							ct.append(j)
							for kk in range(1, len(a)):
								ct.append(i)
							break
						else:
							ct.append(j)
					else:
						if i > a[k]:
							for kk in range(len(a) - k):
								ct.append(i)
							break
						if j > a[k]:
							x = ''.join(map(str, ct)) + str(j) + str(i) * (len(a) - k - 1)
							if int(x) >= n:
								ans = min(ans, int(x))
						if i == a[k]:
							ct.append(i)
							continue
						if j == a[k]:
							ct.append(j)
							continue
						bol = False
						break
				if bol:
					x = int(''.join(map(str, ct)))
					if x >= n:
						ans = min(ans, x)
	print(ans)


from itertools import product
from bisect import bisect_left
output = []

def lprint(*x):
	output.append(' '.join(map(str, x)))
a = sorted(list(set([sum([10 ** ind * x[-ind - 1] for ind in range(l)]) for l in range(2, 11) for i in range(10) for j in range(i + 1, 10) for x in product([i, j], repeat=l)])))
b = sorted([int(str(i) * l) for l in range(1, 11) for i in range(1, 10)])
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lprint(a[bisect_left(a, n)] if k == 2 else b[bisect_left(b, n)])
print(*output, sep='\n')


def get_input():
	al = []
	for c in range(int(input())):
		t = input().split(' ')
		el = [t[0], int(t[1])]
		al.append(el)
	return al

def find_best(n, j, s):
	b = ':'
	m = ':'
	for k in s:
		if k < m:
			m = k
		if n[j] < k and k < b:
			b = k
	if b == ':':
		return False
	else:
		return n[:j] + b + m * (len(n) - j - 1)

def solve(n, k):
	if k == 1:
		for i in range(1, len(n)):
			if n[i] > n[0]:
				return str(int(n[0]) + 1) * len(n)
			elif n[i] < n[0]:
				break
		return n[0] * len(n)
	s = []
	for i in range(len(n)):
		if n[i] not in s:
			if len(s) == k:
				rf = find_best(n, i, s)
				if rf != False:
					return rf
				for j in range(i - 1, -1, -1):
					if n[j] == '9':
						continue
					elif n[j] in n[:j]:
						rf = find_best(n, j, s)
						if rf != False:
							return rf
					else:
						c = str(int(n[j]) + 1)
						cm = c
						for k in range(j):
							if n[k] < cm:
								cm = n[k]
						d = True
						for k in range(0, j):
							if n[k] != c:
								d = False
								break
						if d:
							return n[:j] + c + '0' * (len(n) - j - 1)
						return n[:j] + c + min(cm, c) * (len(n) - j - 1)
			s.append(n[i])
	return n

def main():
	arr_list = get_input()
	for n in arr_list:
		r = solve(n[0], n[1])
		print(r)
main()


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 os
import sys
from io import BytesIO, IOBase
from collections import defaultdict
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 go(n, i, a, b, eq):
	if i == len(n):
		return (True, [])
	if eq:
		if n[i] == a:
			(flag, x) = go(n, i + 1, a, b, True)
			if flag:
				return (True, [a] + x)
		if n[i] < a:
			(flag, x) = go(n, i + 1, a, b, False)
			if flag:
				return (True, [a] + x)
		if n[i] == b:
			(flag, x) = go(n, i + 1, a, b, True)
			if flag:
				return (True, [b] + x)
		if n[i] < b:
			(flag, x) = go(n, i + 1, a, b, False)
			if flag:
				return (True, [b] + x)
		return (False, [])
	else:
		(flag, x) = go(n, i + 1, a, b, False)
		return (True, [a] + x)

def maxDigit(n):
	return str(max((int(d) for d in n)))

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

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 k == 1:
		U = [[D[0], D[0]], [D[0] + 1, D[0] + 1]]
	else:
		U = [[D[0], D[1]], [D[0], D[1] + 1], [D[0] + 1, 0], [D[0], 0]]
	r = 10 ** 20
	for (a, b) in U:
		x = []
		(m, M) = (min(a, b), max(a, b))
		(flag, x) = go(list(map(int, n)), 0, m % 10, M % 10, 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))


def nearest_k_number(a, k):
	c = 0
	ta = a
	while ta != 0:
		ta = ta // 10
		c += 1
	numbers = set()
	counter = 0
	while c != 0:
		c = c - 1
		if c != 0:
			cur = a // 10 ** c
		else:
			cur = a
		cur = cur % 10
		if cur not in numbers:
			counter += 1
			if counter > k:
				return (a // 10 ** (c + 1), a // 10 ** c)
			numbers.add(cur)
	return (a, a)
t = int(input())

def check(n, k):
	c = 0
	s = set()
	while n != 0:
		t = n % 10
		n = n // 10
		if t not in s:
			c += 1
			s.add(t)
		if c > k:
			return True
	return False

def pad(a, k):
	t = a
	m = a % 10
	c = 0
	while t != 0:
		if t % 10 < m:
			m = t % 10
		t //= 10
		c += 1
	while c < k:
		c += 1
		a = a * 10 + m
	return a

def nex(n, k, a0):
	a1 = a0
	nums = set()
	while a0 != 0:
		if a0 % 10 not in nums:
			nums.add(a0 % 10)
		a0 = a0 // 10
	if len(nums) < k:
		while a1 < n:
			a1 *= 10
		return a1
	k = 0
	while n != 0:
		k += 1
		n = n // 10
	return pad(a1, k)

def solve(n, k):
	if k == 1:
		tn = n
		m = -1
		for n in range(1, 10):
			while n < tn:
				n = n * 10 + n % 10
			if m == -1 or m > n:
				m = n
		return m
		return n
	a = nearest_k_number(n, k)
	a0 = a[0]
	a1 = a[1]
	if a0 == n:
		return a0
	at = a0
	pr = False
	while at != 0:
		if at % 10 > a1 % 10:
			pr = True
			break
		at = at // 10
	if pr:
		a0 = a1
	a0 += 1
	while check(a0, k):
		a0 += 1
	a0 = nex(n, k, a0)
	return a0
tn = []
tk = []
while t > 0:
	t = t - 1
	(n, k) = list(map(int, input().strip().split()))
	tn.append(n)
	tk.append(k)
for i in range(len(tk)):
	print(solve(tn[i], tk[i]))


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)


ali = 0
from collections import defaultdict, Counter, deque
ali = 0
ali = 0
ali = 0
from math import sqrt, log10, log, floor, factorial
ali = 0
ali = 0
ali = 0
from bisect import bisect_left, bisect_right
ali = 0
ali = 0
ali = 0
from itertools import permutations, combinations
ali = 0
ali = 0
ali = 0
import sys, io, os
ali = 0
ali = 0
ali = 0
input = sys.stdin.readline
ali = 0
ali = 0
ali = 0
ali = 0
ali = 0
ali = 0
ali = 0
inf = float('inf')
ali = 0
ali = 0
ali = 0
mod = 10 ** 9 + 7
ali = 0
ali = 0

def yn(a):
	print('YES' if a else 'NO')
	ali = 0
ali = 0
ali = 0
ceil = lambda a, b: (a + b - 1) // b
ali = 0
ali = 0
ali = 0
uni = []
ali = 0
ali = 0
ali = 0
strings = {str(i) for i in range(1, 10)}
ali = 0
ali = 0
for i in strings:
	for j in range(1, 11):
		ali = 0
		uni.append(int(i * j))
		ali = 0
		ali = 0
ali = 0
uni.sort()
ali = 0
ali = 0
ali = 0
doubleset = set()
ali = 0
ali = 0

def init(a, b, string):
	ali = 0
	if len(string) >= 10:
		ali = 0
		return
		ali = 0
		ali = 0
	ali = 0
	if string:
		ali = 0
		doubleset.add(int(string))
		ali = 0
		ali = 0
	ali = 0
	init(a, b, string + a)
	ali = 0
	ali = 0
	ali = 0
	init(a, b, string + b)
	ali = 0
	ali = 0
for i in range(10):
	for j in range(i + 1, 10):
		ali = 0
		init(str(i), str(j), '')
		ali = 0
		ali = 0
ali = 0
doub = sorted(doubleset)
ali = 0
ali = 0
ali = 0
t = int(input())
ali = 0
ali = 0
for i in range(t):
	ali = 0
	(n, k) = [int(i) for i in input().split()]
	ali = 0
	ali = 0
	ali = 0
	ncopy = n
	ali = 0
	ali = 0
	ali = 0
	n = str(n)
	ali = 0
	ali = 0
	ali = 0
	s = set(n)
	ali = 0
	ali = 0
	ali = 0
	if len(s) <= k:
		ali = 0
		print(n)
		ali = 0
		ali = 0
		ali = 0
		continue
		ali = 0
		ali = 0
	ali = 0
	if k == 1:
		ali = 0
		print(uni[bisect_left(uni, ncopy)])
		ali = 0
		ali = 0
	else:
		ali = 0
		print(doub[bisect_left(doub, ncopy)])
		ali = 0
		ali = 0


for _ in range(int(input())):
	(n, k) = input().split()
	k = int(k)
	if len(n) == 1:
		print(n)
		continue
	if k == 1:
		f = True
		ff = True
		for u in n:
			if n[0] < u and ff:
				f = False
			elif u < n[0]:
				ff = False
		if f:
			print(n[0] * len(n))
		else:
			print(str(int(n[0]) + 1) * len(n))
	else:
		f = True
		ans = [''] * len(n)
		i1 = -1
		ib = 1
		(a, b) = (n[0], n[1])
		bp1 = str(int(b) + 1)
		(ans[0], ans[1]) = (a, b)
		sf = False
		for i in range(1, len(n)):
			if sf:
				sf = False
				continue
			if f and b == a and (i < len(n) - 1):
				ans[i] = a
				b = n[i + 1]
				bp1 = str(int(b) + 1)
				ib = i + 1
				if b != a:
					f = False
					ans[i + 1] = b
					sf = True
				continue
			if n[i] < min(a, b):
				ans[i] = min(a, b)
				ans = ans[:i + 1] + [min(a, b)] * (len(n) - i - 1)
				break
			elif n[i] == min(a, b):
				ans[i] = min(a, b)
				i1 = i
			elif n[i] < max(a, b):
				ans[i] = max(a, b)
				ans = ans[:i + 1] + [min(a, b)] * (len(n) - i - 1)
				break
			elif n[i] == min(a, b):
				ans[i] = min(a, b)
				i1 = i
			elif n[i] == max(a, b):
				ans[i] = max(a, b)
			else:
				ta = tuple()
				if i1 != -1:
					ans[i1] = max(a, b)
					ans = ans[:i1 + 1] + [min(a, b)] * (len(n) - i1 - 1)
					ta = tuple(ans)
				ans[ib] = bp1
				ans = ans[:ib + 1] + [min(a, bp1) if a != bp1 else '0'] * (len(n) - ib - 1)
				if not ta or tuple(ans) < ta:
					ta = tuple(ans)
				ans = list(ta)
				break
		print(*ans, sep='')


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)]
	d = len(x)
	if k == 1:
		for i in '123456789':
			y = int(i * d)
			if y >= n:
				ans = min(ans, y - n)
		return n + ans
	if len(set(x)) <= 2:
		return n
	d1 = x[0]
	d2 = d1
	for y in x:
		if y != x[0]:
			d2 = y
			break
	bx = [(d1, d2), (d1, 0)]
	if d2 != 9:
		bx += [(d1, d2 + 1)]
	for (d1, d2) in bx:
		if d1 == d2:
			continue
		anss = [d1]
		(d1, d2) = (min(d1, d2), max(d1, d2))
		exc = False
		for i in range(1, len(x)):
			if exc:
				anss += [d1]
				continue
			if x[i] == d1 or x[i] == d2:
				anss += [x[i]]
			else:
				exc = True
				if d1 > x[i]:
					anss += [d1]
				else:
					anss += [d2]
		y = int(''.join((str(k) for k in anss)))
		if y >= n:
			ans = min(ans, y - n)
		anss = [d1]
		(d1, d2) = (min(d1, d2), max(d1, d2))
		exc = False
		for i in range(1, len(x)):
			if exc:
				anss += [d1]
				continue
			if x[i] == d1 or x[i] == d2:
				anss += [x[i]]
			else:
				exc = True
				if d1 > x[i]:
					anss += [d1]
				else:
					anss += [d2]
		y = int(''.join((str(k) for k in anss)))
		if y >= n:
			ans = min(ans, y - n)
		if d1 in x:
			anss = list(x)
			j = 0
			for i in range(len(x)):
				if x[i] == d1:
					j = i
				if x[i] != d1 and x[i] != d2:
					break
			anss[j] = d2
			for i in range(j + 1, len(anss)):
				anss[i] = d1
			y = int(''.join((str(k) for k in anss)))
			if y >= n and len(set(anss)) <= 2:
				ans = min(ans, y - n)
	return ans + n
for _ in range(int(input()) if True else 1):
	(n, k) = map(int, input().split())
	print(solve(n, k))


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)


from math import ceil
import sys
input = sys.stdin.readline
t = int(input())
for j in range(t):
	temp = input().split()
	n = list(temp[0])
	n = [int(x) for x in n]
	k = int(temp[1])
	if k == 1:
		temp = n[0]
		le = len(n)
		for i in range(le - 1):
			if n[i + 1] > n[i]:
				temp += 1
				break
			elif n[i + 1] < n[i]:
				break
		for i in range(le):
			print(temp, end='')
		print()
	else:
		temp1 = n[0]
		temp2 = -1
		ind = -1
		le = len(n)
		for i in range(le - 1):
			if n[i + 1] != n[i]:
				temp2 = n[i + 1]
				ind = i + 1
				break
		if temp2 == -1:
			for i in n:
				print(i, end='')
			print()
			continue
		inde = -1
		for i in range(ind, le):
			if n[i] != temp1 and n[i] != temp2:
				inde = i
				break
		if inde == -1:
			for i in n:
				print(i, end='')
			print()
			continue
		big = max(temp1, temp2)
		small = min(temp1, temp2)
		if n[inde] < small:
			for i in range(inde, le):
				n[i] = small
		elif n[inde] < big:
			for i in range(inde, le):
				n[i] = small
			n[inde] = big
		elif n[inde - 1] == small:
			if n[:inde].count(small) == 1:
				temp = n[:inde].index(small)
				small = small + 1
				n[temp] = small
				if small == big:
					small = 0
				for i in range(temp + 1, le):
					n[i] = small
			else:
				for i in range(inde, le):
					n[i] = small
				n[inde - 1] = big
		else:
			temp = -1
			for i in range(inde):
				if n[i] == small:
					temp = i
			flag = True
			if n[0] == small:
				flag = False
				for i in range(temp):
					if n[i] != small:
						flag = True
						break
			if flag:
				if n[:inde].count(small) == 1:
					temp = n[:inde].index(small)
					small = small + 1
					n[temp] = small
					if small == big:
						small = 0
					for i in range(temp + 1, le):
						n[i] = small
				else:
					n[temp] = big
					for i in range(temp + 1, le):
						n[i] = small
			else:
				n[temp + 1] = big + 1
				for i in range(temp + 2, le):
					n[i] = small
		for i in range(le):
			print(n[i], end='')
		print()


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 getBeautiful(num, k):
	if len(set(str(num))) <= k:
		return num
	unstableIdx = k
	st = str(num)
	set_ = set(st[:unstableIdx + 1])
	while len(set_) <= k:
		set_.add(st[unstableIdx + 1])
		unstableIdx += 1
	digits = set(map(int, set(st[:unstableIdx])))
	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 sys, os
from math import *
from bisect import *
from heapq import *
from collections import *
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		(n, k) = input().split()
		k = int(k)

		def rec(idx, cur, ss):
			nonlocal n, k
			if len(ss) > k or cur < n[:idx]:
				return
			if idx == len(n):
				return cur
			for i in range(10):
				toRem = False
				if str(i) not in ss:
					toRem = True
					ss.add(str(i))
				f = rec(idx + 1, cur + str(i), ss)
				if toRem:
					ss.remove(str(i))
				if f:
					return f
		print(rec(0, '', set()))
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 MI():
	return map(int, input().split())

def outP(var):
	sys.stdout.write(str(var) + '\n')
MOD = 10 ** 9 + 7
mod = 998244353
main()


import os
import sys
from io import BytesIO, IOBase
import math
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 ints_get():
	return map(int, input().strip().split())

def list_get():
	return list(map(int, sys.stdin.readline().strip().split()))

def chars_get():
	return list(map(str, sys.stdin.readline().strip().split()))

def output(to_be_printed, end='\n'):
	sys.stdout.write(str(to_be_printed) + end)

def main():
	v = []
	for i in range(1, 100):
		v.append(i)
	p = []
	for i in range(3, 10):
		s = []
		q = []
		for j in range(i):
			q.append('a')
		s.append(q)
		while len(s) > 0:
			x = s.pop()
			for j in range(len(x)):
				if x[j] == 'a':
					x[j] = 'x'
					if 'a' in x:
						s.append(x.copy())
					else:
						p.append(x.copy())
					x[j] = 'y'
					if 'a' in x:
						s.append(x.copy())
					else:
						p.append(x.copy())
					break
	for i in range(10):
		for j in range(10):
			for k in p:
				w = k.copy()
				for l in range(len(w)):
					if w[l] == 'x':
						w[l] = str(i)
					else:
						w[l] = str(j)
				q = ''
				for h in w:
					q += h
				if v[len(v) - 1] != int(q):
					v.append(int(q))
	v.append(10 ** 9)
	v.sort()
	v2 = []
	for i in range(1, 10):
		for j in range(1, 11):
			q = ''
			for k in range(j):
				q += str(i)
			v2.append(int(q))
	v2.sort()
	o = [v[0]]
	for i in range(1, len(v)):
		if v[i] != o[len(o) - 1]:
			o.append(v[i])
	t = int(input())
	for u in range(t):
		(n, k) = ints_get()
		if k == 1:
			for i in v2:
				if i >= n:
					output(i)
					break
		else:
			for i in o:
				if i >= n:
					output(i)
					break
	return
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))


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


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) = lint()
	if k == 1:
		tmp = str(n)
		if int(tmp[0] * len(tmp)) >= n:
			print(int(tmp[0] * len(tmp)))
		else:
			print(int(str(int(tmp[0]) + 1) * len(tmp)))
	else:
		tmp = bisect.bisect_left(l, n)
		if l[tmp] == n:
			print(n)
		else:
			tmp = bisect.bisect_right(l, n)
			print(l[tmp])


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


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)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m == 1:
		s = str(n)
		if n <= int(s[0] * len(s)):
			print(int(s[0] * len(s)))
		else:
			print(int(str(int(s[0]) + 1) * len(s)))
	else:
		A = list(str(n))
		if min(A) == max(A):
			print(n)
		else:
			x = -1
			s = str(n)
			for i in range(len(A) - 1):
				if A[i] != A[i + 1]:
					x = i + 1
					break
			if n <= int(s[:x + 1] + str(max(int(s[x]), int(s[x - 1]))) * (len(s) - x - 1)):
				Ans = s[:x + 1]
				mi = str(min(int(s[x]), int(s[x - 1])))
				ma = str(max(int(s[x]), int(s[x - 1])))
				for i in range(x + 1, len(s)):
					if int(Ans + mi + ma * (len(s) - i - 1)) >= n:
						Ans += mi
					else:
						Ans += ma
				print(Ans)
			elif int(s[x]) + 1 == int(s[0]):
				print(int(s[:x] + str(int(s[x]) + 1) + '0' * (len(s) - x - 1)))
			else:
				print(int(s[:x] + str(int(s[x]) + 1) + str(min(int(s[x]) + 1, int(s[x - 1]))) * (len(s) - x - 1)))


import sys, itertools, bisect
res1 = set()
res2 = set()
for l in range(1, 3):
	for i in itertools.combinations([a for a in range(10)], l):
		for j in range(1, 11):
			for k in itertools.product(i, repeat=j):
				if k[0] == 0:
					continue
				if l == 1:
					res1.add(int(''.join(map(str, k))))
				else:
					res2.add(int(''.join(map(str, k))))
res1 = sorted(res1)
res2 = sorted(res2)
tc = int(sys.stdin.readline())
for _ in range(tc):
	(n, k) = map(int, sys.stdin.readline().split())
	if k == 1:
		print(res1[bisect.bisect_left(res1, n)])
	else:
		print(res2[bisect.bisect_left(res2, n)])


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 bisect import *

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 = []
	for i in n1:
		if len(digs) == k - 1:
			break
		if i not in digs:
			digs.append(i)
	for i in range(10):
		(cur, lst, flag) = ([], [-1, 0], 0)
		if str(i) not in digs:
			digs.append(str(i))
			flag = 1
		digs.sort()
		for j in n1:
			ix = bisect_left(digs, j)
			if ix < len(digs):
				cur.append(digs[ix])
				if j < digs[ix]:
					cur.extend([digs[0]] * (ln - len(cur)))
				if ix != len(digs) - 1:
					lst = [len(cur) - 1, ix + 1]
			else:
				if lst[0] == -1:
					cur = ['9'] * 10
					break
				cur[lst[0]] = digs[lst[1]]
				cur = cur[:lst[0] + 1] + [digs[0]] * (ln - lst[0] - 1)
				break
			if len(cur) == len(n1):
				break
		if flag:
			digs.remove(str(i))
		ans = min(ans, int(''.join(cur)))
	print(ans)


from itertools import product
from bisect import bisect_left
from sys import stdin
input = lambda : stdin.readline().strip()
linput = lambda : [*map(int, input().split())]
output = []

def lprint(*x):
	output.append(' '.join(map(str, x)))

def main():
	(n, k) = linput()
	if k == 2:
		lprint(a[bisect_left(a, n)])
	else:
		lprint(b[bisect_left(b, n)])
a = []
for l in range(2, 11):
	for i in range(10):
		for j in range(i + 1, 10):
			for x in product([i, j], repeat=l):
				v = 0
				for ind in range(l):
					v += 10 ** ind * x[-ind - 1]
				a.append(v)
b = []
for l in range(1, 11):
	for i in range(1, 10):
		b.append(int(str(i) * l))
a.sort()
b.sort()
for _ in ' ' * int(input()):
	main()
print(*output, sep='\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)
	suffix = str(min(prefix) * (len(n) - len(prefix)))
	print(prefix + suffix)


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


import os, sys, math
from io import BytesIO, IOBase
ip = lambda : input()
it = lambda : int(input())
ma = lambda : map(int, input().split(' '))
li = lambda : list(map(int, input().split(' ')))
mod = 10 ** 9 + 7

def m1(n, l):
	return n * l

def solve(a, b, s, l):
	x = a
	t = 1
	(g, h) = (min(a, b), max(a, b))
	for i in range(1, l):
		if x + g + h * (l - t - 1) >= s:
			x += g
			t += 1
		else:
			x += h
			t += 1
	return x

def main():
	for _ in range(int(input())):
		(n, k) = ma()
		s = str(n)
		l = len(s)
		ans = m1(s[0], l)
		if ans < s:
			ans = m1(str(int(s[0]) + 1), l)
		if k == 1:
			print(ans)
			continue
		if s == s[0] * l:
			print(s)
			continue
		i = 1
		while s[i] == s[0]:
			i += 1
		z = solve(s[0], s[i], s, l)
		if z >= s and ans > z:
			ans = z
		if ord(s[0]) - ord(s[i]) == 1:
			g = '0'
		else:
			g = str(int(s[i]) + 1)
		z = solve(s[0], g, s, l)
		if z >= s and ans > z:
			ans = z
		print(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 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))


import itertools
import bisect
a1 = []
m = 1
for j in itertools.combinations(range(10), m):
	for n in range(1, 10):
		for i in itertools.product(*[j] * n):
			if i[0] != 0 and len(set(i)) == m:
				a1.append(int(''.join(map(str, i))))
a1.sort()
a2 = a1.copy()
m = 2
for j in itertools.combinations(range(10), m):
	for n in range(1, 10):
		for i in itertools.product(*[j] * n):
			if i[0] != 0 and len(set(i)) == m:
				a2.append(int(''.join(map(str, i))))
a2.sort()
for i in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 10 ** 9:
		if k == 2:
			print(n)
			continue
		else:
			print('1111111111')
			continue
	if k == 1:
		w = bisect.bisect_right(a1, n)
		if w > 0 and a1[w - 1] == n:
			print(n)
		else:
			print(a1[w])
	else:
		w = bisect.bisect_right(a2, n)
		if w > 0 and a2[w - 1] == n:
			print(n)
		else:
			print(a2[w])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(n)
	m = int(len(s) * '1')
	for i in range(1, 10):
		if i * m >= n:
			ans = i * m
			break
	if k == 2:
		for i in range(9):
			for j in range(i + 1, 10):
				flag = 0
				for x in range(len(s)):
					if int(s[x]) < j:
						if int(s[x]) < i:
							ans = min(ans, int(s[:x] + str(i) * (len(s) - x)))
						ans = min(ans, int(s[:x] + str(j) + str(i) * (len(s) - x - 1)))
					if s[x] != str(i) and s[x] != str(j):
						flag = 1
						break
				if not flag:
					ans = n
	print(ans)


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


a = []
for i in range(10):
	for j in range(i, 10):
		for m in range(1, 11):
			for k in range(2 ** m):
				b = bin(k)[2:]
				b = '0' * (m - len(b)) + b
				y = ''
				for l in b:
					if l == '0':
						y += str(i)
					else:
						y += str(j)
				if int(y) > 0:
					a.append(int(y))
a.sort()
for i in range(int(input())):
	(n, k) = input().split()
	k = int(k)
	if k == 1:
		if int(n[0] * len(n)) >= int(n):
			print(n[0] * len(n))
		elif n[0] == '9':
			print('1' * (len(n) + 1))
		else:
			print(str(int(n[0]) + 1) * len(n))
	else:
		l = -1
		r = len(a)
		n = int(n)
		while r - l > 1:
			m = (l + r) // 2
			if a[m] < n:
				l = m
			else:
				r = m
		print(a[r])


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)


import sys
input = lambda : sys.stdin.readline().strip()

def solve():
	(n, k) = map(int, input().split())
	s = str(n)
	if len(set(s)) <= k:
		return n
	L = len(s)

	def helper(a, b):
		i = 0
		while i < len(s) and s[i] in a + b:
			i += 1
		if s[i] > b:
			j = i - 1
			while j >= 0 and s[j] == b:
				j -= 1
			if j >= 0:
				return s[:j] + b + a * (L - j - 1)
			else:
				return '9' * L
		elif s[i] < a:
			return s[:i] + a * (L - i)
		else:
			return s[:i] + b + a * (L - i - 1)
	if k == 1:
		i = 0
		while s[i] == s[0]:
			i += 1
		if s[i] < s[0]:
			res = s[0] * L
		else:
			c = str(int(s[0]) + 1)
			res = c * L
	else:
		res = min((helper(str(a), str(b)) for a in range(10) for b in range(a + 1, 10)))
	return res
for _ in range(int(input())):
	print(solve())


import sys
from itertools import product
from bisect import bisect_left as bisect
input = sys.stdin.readline

def main():
	os = [1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111]

	def tonum(ar):
		ans = 0
		for x in ar:
			ans *= 10
			ans += int(x)
		return ans
	t = int(input())
	twos = []
	for i in range(10):
		for j in range(i + 1, 10):
			for l in range(10):
				for mask in range(1 << l):
					q = 0
					for b in range(l):
						if mask >> b & 1:
							q *= 10
							q += i
						else:
							q *= 10
							q += j
					twos.append(q)
	twos.sort()
	for _ in range(t):
		(n, k) = input().split()
		k = int(k)
		l = len(n)
		if k == 1:
			o = os[l - 1]
			nn = tonum(n)
			for i in range(1, 10):
				if o * i >= nn:
					print(o * i)
					break
			continue
		if l == 10:
			print(1000000000)
			continue
		if k == 2 and l == 1:
			print(n)
			continue
		nn = tonum(n)
		print(twos[bisect(twos, nn)])
main()


def recurs(i, n, dist, nw, k, orig):
	if dist > k:
		return ''
	if nw[0:i] < orig[0:i]:
		return ''
	if i >= n:
		return nw
	c = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
	for item in c:
		nw = nw[:i] + item + nw[i + 1:]
		f = False
		for j in range(i):
			if nw[j] == item:
				f = True
				break
		cc = recurs(i + 1, n, dist + (f == False), nw, k, orig)
		if cc != '':
			return cc
	return ''
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	n = str(n)
	nw = '0' * len(n)
	print(recurs(0, len(n), 0, nw, k, n))


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
	for se in bits[k]:
		if max(se) * times < int(n):
			continue
		tmp = -1
		nex = [-1] * 10
		for i in range(9, -1, -1):
			if i in se:
				tmp = i
			nex[i] = tmp
		ans = []
		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 sys
input = sys.stdin.readline
ans1 = set()
ans2 = set()
for a in range(10):
	ans = a
	for i in range(10):
		ans1.add(ans)
		ans = ans * 10 + a
for a in range(10):
	for b in range(10):
		for k in range(2, 11):
			for bit in range(2 ** k):
				x = 0
				for i in range(k):
					bitcnt = 0
					if bit >> i & 1:
						x = x * 10 + a
						bitcnt += 1
					else:
						x = x * 10 + b
				if not (bitcnt == 0 or bitcnt == k):
					ans2.add(x)
ans1 = list(ans1)
ans2 = list(ans2)
ans1.sort()
ans2.sort()

def bilower(a, x):
	if len(a) == 0:
		return -1
	mi = 0
	ma = len(a) - 1
	if a[0] > x:
		return -1
	if a[ma] <= x:
		return ma
	while ma - mi > 1:
		mid = (ma + mi) // 2
		if a[mid] <= x:
			mi = mid
		else:
			ma = mid
	return mi

def bihigher(a, x):
	if len(a) == 0:
		return 0
	mi = 0
	ma = len(a) - 1
	if a[ma] < x:
		return ma + 1
	if a[0] >= x:
		return 0
	while ma - mi > 1:
		mid = (ma + mi) // 2
		if a[mid] >= x:
			ma = mid
		else:
			mi = mid
	return ma

def birange(a, l, r):
	left = bihigher(a, l)
	right = bilower(a, r)
	return right - left + 1
T = int(input())
for iiii in range(T):
	(n, k) = map(int, input().split())
	if k == 1:
		print(ans1[bihigher(ans1, n)])
	else:
		print(ans2[bihigher(ans2, n)])


from bisect import *
import sys
input = sys.stdin.readline

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

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
fi = [int('1' * 10)]
for i in range(1, 10):
	for j in range(1, 11):
		x = str(i) * j
		fi.append(int(x))
se = [int('1' * 10), 10 ** 9]
for i in range(2, 10):
	for j in range(10):
		for k1 in range(10):
			for k2 in range(2 ** i):
				nu = ''
				z = bin(k2)[2:]
				z = z.zfill(i)
				for k3 in range(i):
					if z[k3] == '1':
						nu += str(j)
					else:
						nu += str(k1)
				se.append(int(nu))
fi.sort()
se.sort()
fk = float('inf')
while t:
	t -= 1
	(n, k) = ma()
	if k == 1:
		z = bisect_left(fi, n)
		print(fi[z])
	else:
		z = bisect_left(se, n)
		print(se[z])


t = int(input())
results = []
for i in range(t):
	(n, k) = input().split()
	k = int(k)
	if k == 1:
		digits = len(n)
		important_num = int(digits * '1')
		n = int(n)
		for j in range(1, 10):
			if important_num * j >= n:
				results.append(important_num * j)
				break
		else:
			results.append((digits + 1) * '1')
	elif k == 2:
		digits_num = len(n)
		digits = [int(c) for c in n]
		num_results = []
		a = digits[0]
		char_a = n[0]
		for b in range(0, 10):
			char_b = str(b)
			current_num = ''
			for digit in digits:
				if digit > a:
					if digit > b:
						break
					elif digit < b:
						current_num += char_b + char_a * (digits_num - len(current_num) - 1)
						num_results.append(current_num)
						break
					else:
						current_num += char_b
				elif digit < a:
					if digit > b:
						current_num += char_a + char_b * (digits_num - len(current_num) - 1)
						num_results.append(current_num)
						break
					elif digit < b:
						if a < b:
							current_num += char_a * (digits_num - len(current_num))
							num_results.append(current_num)
							break
						else:
							current_num += char_b * (digits_num - len(current_num))
							num_results.append(current_num)
							break
					else:
						num_results.append(current_num + char_a + char_b * (digits_num - len(current_num) - 1))
						current_num += char_b
				elif digit > b:
					current_num += char_a
				elif digit < b:
					num_results.append(current_num + char_b + char_a * (digits_num - len(current_num) - 1))
					current_num += char_a
				else:
					current_num += char_a
			else:
				num_results.append(current_num)
		if n[0] == 9:
			num_results.append('1' + digits_num * '0')
		else:
			num_results.append(str(digits[0] + 1) + (digits_num - 1) * '0')
		results.append(min([int(item) for item in num_results]))
for i in range(t):
	print(results[i])


from sys import stdin, stdout

def INPUT():
	return list((int(i) for i in stdin.readline().split()))

def inp():
	return stdin.readline()

def out(x):
	return stdout.write(x)
import math
INT_MAX = 10 ** 13
from bisect import bisect_left
import sys
MOD = 10 ** 9 + 7
inf = MOD ** 2
from decimal import *

def calc(n):
	A = list((int(ele) for ele in list(str(n))))
	bool = False
	for i in range(1, len(A)):
		if A[i] != A[i - 1]:
			if A[i] > A[i - 1]:
				bool = True
				x = A[i - 1]
			break
	if bool is True:
		return str(x + 1) * len(A)
	else:
		return str(A[0]) * len(A)

def special(a, b, n):
	l = len(str(n))
	X = []
	for i in range(1 << l):
		ans = ''
		for j in range(l):
			if 1 << j & i:
				ans += str(a)
			else:
				ans += str(b)
		X.append(ans)
	return X
D = []
for k in range(1, 10):
	first = []
	for i in range(10):
		for j in range(i + 1, 10):
			for ele in special(i, j, 10 ** k):
				if int(ele) >= 10 ** k:
					first.append(int(ele))
	first.sort()
	D.append(first)

def calc2(n):
	if n == 10 ** 9 or len(set(list(str(n)))) == 1 or n <= 100:
		return n
	l = len(str(n))
	X = D[l - 2]
	ans = inf
	return X[bisect_left(X, n)]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k == 1:
		out(str(calc(n)) + '\n')
	else:
		out(str(calc2(n)) + '\n')


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 bisect
l = []
c = '0123456789'
for i in c:
	for j in c:
		z = [i, j]
		for k in z:
			z += [k + i, k + j]
			if len(k) > 10:
				break
		l += z
l = list(set(l))
(x, y) = ([], [])
for i in l:
	if len(set(i)) == 1:
		x += [i]
	else:
		y += [i]
x = sorted(map(int, x))
y = sorted(map(int, y))
for i in range(int(input())):
	(n, k) = map(int, input().split())
	q = set(str(n))
	if len(q) > k:
		if k == 1:
			print(x[bisect.bisect(x, n)])
		else:
			print(y[bisect.bisect(y, n)])
	else:
		print(n)


def F1(s, k):
	siz = len(s)
	pivot = s[0]
	index = 1
	while index < siz:
		if s[index] != pivot:
			break
		else:
			index += 1
	if index == siz:
		return s
	elif pivot > s[index]:
		res = s[:index]
		return replaceF(res, pivot, index, siz)
	else:
		res = ''
		ch = str(int(pivot) + 1)
		return replaceF(res, ch, 0, siz)

def replaceF(res, f, start, siz):
	for i in range(start, siz):
		res += f
	return res

def F2(s, k):
	siz = len(s)
	f1 = s[0]
	index = 1
	while index < siz:
		if s[index] != f1:
			break
		else:
			index += 1
	if index == siz:
		return s
	f2 = s[index]
	pos = index + 1
	while pos < siz:
		if s[pos] != f1 and s[pos] != f2:
			break
		else:
			pos += 1
	if pos == siz:
		return s
	minF = min(f1, f2)
	maxF = max(f1, f2)
	maxInt = int(maxF)
	minInt = int(minF)
	if s[pos] < minF:
		res = s[:pos]
		return replaceF(res, minF, pos, siz)
	elif s[pos] < maxF:
		res = s[:pos]
		res += maxF
		return replaceF(res, minF, pos + 1, siz)
	elif s[pos - 1] == minF:
		res = s[:pos - 1]
		if minF not in res:
			res += str(minInt + 1)
			if maxInt > minInt + 1:
				minF = str(minInt + 1)
			else:
				minF = str(0)
		else:
			res += maxF
		return replaceF(res, minF, pos, siz)
	else:
		stand = pos - 1
		while stand >= 0:
			if s[stand] == minF:
				break
			else:
				stand -= 1
		option = False
		for i in range(stand, -1, -1):
			if s[i] == maxF:
				option = True
				break
		if option:
			res = s[:stand]
			if minF not in res:
				res += str(minInt + 1)
				if maxInt > minInt + 1:
					minF = str(minInt + 1)
				else:
					minF = str(0)
			else:
				res += maxF
			return replaceF(res, minF, stand + 1, siz)
		else:
			res = s[:stand + 1]
			res += str(int(maxF) + 1)
			return replaceF(res, minF, stand + 2, siz)
case = int(input())
for t in range(case):
	(s, tmp) = input().split()
	k = int(tmp)
	if k == 1:
		print(F1(s, k))
	else:
		print(F2(s, k))


def check(s, k, t, n):
	z = set()
	for i in range(len(s)):
		if i == len(s) - 1:
			z.add(t)
		else:
			z.add(int(s[i]))
	if len(z) <= k:
		needed = len(str(n)) - len(s)
		arr = []
		min_val = 9
		for i in range(len(s)):
			if i == len(s) - 1:
				arr.append(t)
				if t < min_val:
					min_val = t
			else:
				arr.append(int(s[i]))
				if int(s[i]) < min_val:
					min_val = int(s[i])
		if len(z) == k:
			for i in range(needed):
				arr.append(min_val)
		else:
			for i in range(needed):
				arr.append(0)
		for i in range(len(arr)):
			print(arr[i], end='')
		print()
		return True
	return False

def func(n, i, k):
	s = str(n)[0:i + 1]
	t = int(s[-1]) + 1
	while t < 10:
		if check(s, k, t, n):
			return 0
		else:
			t += 1
	func(n, i - 1, k)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = len(str(n))
	if check(str(n), k, int(str(n)[-1]), n):
		continue
	func(n, l - 1, k)


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)


from collections import defaultdict, Counter

def func(s, k, i, ns):
	global vis, res
	if len(vis) > k:
		return False
	if s[0:i] > ns[0:i]:
		return False
	if i >= len(s):
		res = min(res, int(''.join(ns)))
		return True
	for j in range(0, 10):
		if i == 0 and j == 0:
			continue
		vis[j] += 1
		if func(s, k, i + 1, ns + [str(j)]):
			return True
		vis[j] -= 1
		if vis[j] <= 0:
			del vis[j]
	return False
test = int(input())
for t in range(test):
	(n, k) = map(int, input().split())
	s = list(str(n))
	f = Counter(s)
	res = float('inf')
	if k == 1 and len(f) == 1 or (k == 2 and f == 2):
		print(n)
		continue
	if k == 1:
		m = len(s)
		number = ''.join('1' * m)
		number = int(number)
		for i in range(1, 10):
			if i * number >= n:
				res = i * number
				break
	else:
		vis = defaultdict(int)
		_ = func(s, k, 0, [])
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	n = str(n)
	stack = [['', 0]]
	l = len(n)
	store = ''
	while stack:
		(num, loop) = stack.pop()
		if len(num) == l and len(set(num)) <= k:
			store = num
			break
		flag = 0
		for i in range(loop, 10):
			nn = num + str(i)
			if int(nn) >= int(n[:len(num) + 1]) and len(set(nn)) <= k:
				stack.append([nn, 0])
				flag = 1
				break
		if flag == 0:
			stack.append([num[:-1], int(num[-1]) + 1])
	print(store)


import bisect
import itertools
import sys
input = sys.stdin.readline
t = int(input())
s1 = set()
s2 = set()
for i in range(1, 11):
	p = [j for j in range(i)]
	for j in range(1, i + 1):
		for p0 in itertools.combinations(p, j):
			for k in range(10):
				x = [str(k)] * i
				s1.add(int(''.join(x)))
				s2.add(int(''.join(x)))
				for l in range(k + 1, 10):
					for m in p0:
						x[m] = str(l)
					s2.add(int(''.join(x)))
s1 = list(s1)
s1.sort()
s2 = list(s2)
s2.sort()
for _ in range(t):
	(n, k) = map(int, input().split())
	if k == 1:
		ans = s1[bisect.bisect_left(s1, n - 0.5)]
	else:
		ans = s2[bisect.bisect_left(s2, n - 0.5)]
	print(ans)


from itertools import product
from bisect import bisect_left
from sys import stdin
input = lambda : stdin.readline().strip()
linput = lambda : [*map(int, input().split())]
output = []

def lprint(*x):
	output.append(' '.join(map(str, x)))

def main():
	(n, k) = linput()
	if k == 2:
		lprint(a[bisect_left(a, n)])
	else:
		lprint(b[bisect_left(b, n)])
a = set()
for l in range(2, 11):
	for i in range(10):
		for j in range(i + 1, 10):
			for x in product([i, j], repeat=l):
				a.add(sum([10 ** ind * x[-ind - 1] for ind in range(l)]))
b = sorted([int(str(i) * l) for l in range(1, 11) for i in range(1, 10)])
a = sorted(list(a))
for _ in ' ' * int(input()):
	main()
print(*output, sep='\n')


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)


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
from collections import Counter
for t in range(int(input())):
	(n, k) = map(int, input().split())
	L = len(str(n))
	if k == 1:
		for x in range(1, 10):
			cur = int(str(x) * L)
			if cur >= n:
				print(cur)
				break
	else:
		for x in range(1, 10):
			cur = int(str(x) * L)
			if cur >= n:
				break
		for x in range(10):
			for y in range(x + 1, 10):
				(x, y) = (str(x), str(y))
				flag = 0
				tmp = ''
				flag2 = 0
				last = {}
				for (i, c) in enumerate(str(n)):
					if not flag:
						if c == x or c == y:
							tmp += c
						elif x > c:
							tmp += x
							flag = 1
						elif y > c:
							tmp += y
							flag = 1
						else:
							if x not in last:
								flag2 = 1
							else:
								tmp = str(n)[:last[x]] + y + x * (L - 1 - last[x])
							break
					else:
						tmp += x
					last[c] = i
				if flag2:
					continue
				if tmp[0] == '0':
					continue
				cur = min(cur, int(tmp))
		print(cur)


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


import sys
inputt = sys.stdin.readline
printt = sys.stdout.write
import math
import functools
from collections import deque
import heapq
from queue import PriorityQueue

def get():
	return inputt().split()

def getint():
	return int(inputt())

def getints():
	return map(int, inputt().split())
h1 = [i * int('1' * j) for i in range(1, 10) for j in range(1, 10)]
h1.sort()

def find(h, n):
	if len(h) == 1:
		return h[0]
	mid = len(h) // 2
	if h[mid - 1] < n and n <= h[mid]:
		return h[mid]
	elif n <= h[mid - 1]:
		return find(h[:mid], n)
	else:
		return find(h[mid:], n)
h2 = []
for (i, j) in [(i, j) for i in range(0, 10) for j in range(i, 10)]:
	x = {i: set() for i in range(1, 10)}
	x[0] = {''}
	for k in range(9):
		for st in x[k]:
			x[k + 1].add(st + str(i))
			x[k + 1].add(st + str(j))
		h2.extend(map(int, x[k + 1]))
h2.sort()
for _ in range(getint()):
	(n, k) = getints()
	if n == 10 ** 9:
		if k == 1:
			print(1111111111)
		else:
			print(n)
	elif k == 1:
		print(find(h1, n))
	else:
		print(find(h2, n))


from itertools import product
from bisect import bisect_left
from sys import stdin
input = stdin.readline
l1 = [0]
s = set()
l2 = []

def kone():
	for i in range(1, 10):
		for j in range(1, 11):
			l1.append(int(str(i) * j))
	l1.sort()

def ktwo():
	s = set(l1)
	for i in range(9):
		for j in range(i + 1, 10):
			for k in range(2, 11):
				for v in product(str(i) + str(j), repeat=k):
					val = ''.join(v)
					if val not in s:
						l2.append(int(val))
	l2.sort()
kone()
ktwo()
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k == 1:
		idx = bisect_left(l1, n)
		print(l1[idx])
	else:
		idx = bisect_left(l2, n)
		print(l2[idx])


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = []
	while n > 0:
		l.insert(0, n % 10)
		n = n // 10
	digit = set()
	ans = []
	idx = 0
	while len(digit) < k - 1:
		digit.add(l[idx])
		ans.append(l[idx])
		idx += 1
	while idx < len(l) and l[idx] in digit:
		ans.append(l[idx])
		idx += 1
	if len(ans) < len(l):
		tmp = idx
		digit.add(l[idx])
		Ma = max(digit)
		fix = idx
		while tmp < len(l) and l[tmp] in digit:
			if l[tmp] < Ma:
				fix = tmp
			tmp += 1
		if tmp < len(l) and max(digit) > l[tmp]:
			for i in range(idx, tmp):
				ans.append(l[i])
			M = Ma
			for item in digit:
				if item > l[tmp]:
					M = min(M, item)
			ans.append(M)
			m = min(digit)
			for _ in range(tmp + 1, len(l)):
				ans.append(m)
		elif tmp < len(l) and max(digit) < l[tmp]:
			if fix != idx:
				M = Ma
				for item in digit:
					if item > l[fix]:
						M = min(M, item)
				for i in range(idx, fix):
					ans.append(l[i])
				ans.append(M)
				m = min(digit)
				for i in range(fix + 1, len(l)):
					ans.append(m)
			elif fix == idx:
				digit.remove(l[idx])
				ans.append(l[idx] + 1)
				if l[idx] + 1 in digit:
					for i in range(idx + 1, len(l)):
						ans.append(0)
				else:
					digit.add(l[idx] + 1)
					m = min(digit)
					for i in range(idx + 1, len(l)):
						ans.append(m)
		else:
			for i in range(idx, tmp):
				ans.append(l[i])
	tot = ans[0]
	for i in range(1, len(ans)):
		tot *= 10
		tot += ans[i]
	print(tot)


def solve(num, k):
	count = 0
	tab = [-1 for _ in range(int(k))]
	idx = 0
	rem = -1
	rem_idx = -1
	for x in num:
		if int(x) not in tab:
			if count < int(k):
				tab[count] = int(x)
				count += 1
			else:
				rem = int(x)
				rem_idx = idx
				break
		idx += 1
	if rem == -1:
		print(num)
		return
	idx_1 = 0
	check = False
	counter = 0
	sec_tab = []
	new = min(tab)
	if max(rem, max(tab)) == rem:
		for x in range(rem_idx, -1, -1):
			if int(num[x]) < max(tab):
				idx_1 = x
				break
		for x in range(rem_idx + 1):
			if int(num[x]) not in sec_tab:
				if counter == count - 1:
					idx_2 = x
					break
				else:
					counter += 1
					sec_tab.append(int(num[x]))
		if idx_2 >= idx_1:
			counter = 0
			for x in num:
				if int(x) not in sec_tab and (not check):
					print(int(x) + 1, end='')
					check = True
					if int(x) + 1 not in sec_tab:
						sec_tab.append(int(x) + 1)
					if len(sec_tab) == count:
						new = min(sec_tab)
					else:
						new = 0
				elif not check:
					print(int(x), end='')
				else:
					print(new, end='')
			print()
		else:
			temp = min([i for i in tab if i > int(num[idx_1])])
			for j in range(len(num)):
				if j < idx_1:
					print(num[j], end='')
				elif j == idx_1:
					print(temp, end='')
				else:
					print(min(tab), end='')
			print()
	else:
		temp = min([i for i in tab if i > rem])
		for x in num:
			if int(x) not in sec_tab and (not check):
				if counter == count:
					print(temp, end='')
					check = True
				else:
					sec_tab.append(int(x))
					counter += 1
					print(int(x), end='')
			elif not check:
				print(int(x), end='')
			else:
				print(min(tab), end='')
		print()
for i in range(int(input())):
	(num, k) = map(str, input().split())
	solve(num, k)