Chef Leonardo has a decimal integer $N$ and a non-zero decimal digit $d$. $N$ does not contain the digit zero; specifically, $N$ should always be treated as a decimal integer without leading zeroes.
Chef likes $d$ and does not like any other digit, so he decided to change $N$. He may apply the following operation any number of times (including zero): append the digit $d$ to the decimal representation of $N$ ($d$ becomes the least significant digit of $N$), then remove one occurrence of one digit from the decimal representation of $N$.
Chef has already changed a lot of numbers and he got bored. Now, he wants to know the smallest possible value of $N$ which can be obtained by performing the operation described above. Can you help him?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $d$.

-----Output-----
For each test case, print a single line containing one integer - the minimum number Chef can obtain.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 10^{18}$
- $N$ does not contain the digit $0$
- $1 \le d \le 9$

-----Subtasks-----
Subtask #1 (40 points):
- $1 \le T \le 100$
- $1 \le N \le 10^9$
Subtask #2 (60 points): original constraints

-----Example Input-----
3
35 4
42 4
24 9

-----Example Output-----
34
24
24

-----Explanation-----
Example case 1: Chef can remove the digit $5$ and add $4$ to the end of $N$. Then, $N$ becomes $34$.
Example case 2: Chef can remove the digit $4$ from the beginning of $N$, add $4$ to the end of $N$ and get $N = 24$.
Example case 3: Chef cannot make his number any smaller.

Difficulty: MEDIUM
Tags: Mathematics

Implementation

Starter code:

Solutions:
for _ in range(int(input())):
	(n, d) = input().split()
	a = list(n)
	w = int(d)
	count = 1
	l = []
	while 1:
		if count != len(a):
			count = 1
			for i in range(len(a) - 1):
				if int(a[i]) > int(a[i + 1]):
					a.pop(i)
					a.append(d)
					break
				else:
					count += 1
		else:
			for i in range(len(a)):
				if int(a[i]) >= w:
					l.append(a[i])
					a.append(d)
				elif int(a[i]) == w:
					break
			break
	for i in l:
		a.remove(i)
	print(''.join(a))


def show(t):
	for _ in range(t):
		(a, n) = map(int, input().rstrip().split())
		res = []
		res1 = []
		a = str(a)
		for i in a:
			res.append(int(i))
		a = n
		for i in range(len(res) - 1, -1, -1):
			if a >= res[i]:
				a = res[i]
				res1.append(a)
		for i in range(len(res1) - 1, -1, -1):
			print(res1[i], end='')
		for i in range(len(res) - len(res1)):
			print(n, end='')
		print('')
show(int(input()))


for __ in range(int(input())):
	(N, d) = tuple(map(int, input().split()))
	current_num = list(map(int, list(str(N))))
	length = len(current_num)
	while True:
		for i in range(1, length + 1):
			if i == length:
				num = current_num[i - 1]
				if num > d:
					del current_num[i - 1]
					current_num.append(d)
					break
			else:
				num = current_num[i - 1]
				if num > current_num[i]:
					del current_num[i - 1]
					current_num.append(d)
					break
		else:
			break
	num = ''
	for digit in current_num:
		num += str(digit)
	print(num)


t = int(input())
for i in range(t):
	(a, k) = input().split(' ')
	k = int(k)
	arr = [int(l) for l in a]
	num = '0'
	while len(arr) > 0:
		mini = 10
		ind = 0
		for z in range(len(arr)):
			if arr[z] < mini:
				mini = arr[z]
				ind = z
		if mini < k:
			num += str(mini)
			if ind + 1 < len(arr):
				arr = arr[ind + 1:]
			else:
				break
		else:
			break
	if len(a) > len(num) - 1:
		for j in range(len(a) - (len(num) - 1)):
			num += str(k)
	print(int(num))


t = int(input())
for i in range(t):
	(N, d) = map(str, input().split(' '))
	min = int(d)
	N = list(N)
	count = 0
	for i in range(len(N) - 1, -1, -1):
		if int(N[i]) > min:
			N[i] = ''
			count += 1
		else:
			min = int(N[i])
	print(''.join(N) + d * count)


T = int(input())
for i in range(T):
	(n, d) = input().split()
	d = int(d)
	a = []
	l = len(n)
	mn = d
	for j in range(l):
		a.append(int(n[j]))
	for k in range(l - 1, -1, -1):
		if a[k] > mn:
			a.pop(k)
			a.append(d)
		mn = min(mn, a[k])
	print(*a, sep='', end='\n')
	T = T - 1


h = int(input())
for z in range(h):
	(a, b) = map(int, input().split())
	s = []
	k = 0
	c = 0
	while a > 0:
		r = a % 10
		s.append(r)
		a = a // 10
	s.reverse()
	n = len(s)
	for i in range(0, n):
		if s[i] >= b:
			s.remove(s[i])
			s.append(b)
	while c < n - 1:
		if s[c] > s[c + 1]:
			s.remove(s[c])
			s.append(b)
			c = -1
		c += 1
	for i in range(0, n):
		k = k * 10 + s[i]
	print(k)


t = int(input())
while t > 0:
	(num, n) = input().split()
	a = list(map(int, num))
	mi = min(a)
	n = int(n)
	l = len(a)
	l1 = l
	if mi < n:
		last = l - a[::-1].index(mi) - 1
		c = 0
		while last < l:
			cmi = a.count(mi)
			for k in range(cmi):
				print(mi, end='')
				c = c + 1
			if last == l - 1:
				break
			a = a[last + 1:]
			mi = min(a)
			if mi >= n:
				break
			l = len(a)
			last = l - a[::-1].index(mi) - 1
		while c < l1:
			print(n, end='')
			c = c + 1
	else:
		for i in range(l1):
			print(n, end='')
	print()
	t = t - 1


for i in range(int(input())):
	(n, d) = input().split()
	l = list(n)
	s = list(n)
	p = d
	k = 0
	for j in range(len(l) - 1, -1, -1):
		if n[j] > p:
			s[j] = ''
			k += 1
		else:
			p = s[j]
	s = ''.join(s) + d * k
	print(s)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = list(str(n))
	l = len(s)
	s1 = ''
	if int(min(s)) > k:
		for i in range(l):
			s1 += str(k)
		print(s1)
	else:
		c = min(s)
		while int(c) != k and len(s) != 0:
			s1 += c
			ind = s.index(c)
			s = s[ind + 1:]
			for i in range(ind + 1):
				s.append(str(k))
			c = min(s)
		z = len(s1)
		for i in range(l - z):
			s1 += str(k)
		print(s1)


T = int(input())
while T != 0:
	T = T - 1
	(N, d) = map(int, input().split())
	digits = [int(i) for i in list(str(N))]
	change = True
	digits.append(d)
	while change != False:
		change = False
		for i in range(0, len(digits) - 1):
			if digits[i] > digits[i + 1]:
				change = True
				digits.pop(i)
				digits.append(d)
				break
	digits.pop()
	ans = ''.join(map(str, digits))
	ans = int(ans)
	print(ans)


t = int(input())
while t:
	(n, d) = map(int, input().split())
	n = str(n)
	temp = n
	for x in range(1, 10):
		x = str(x)
		stack = []
		count = 0
		for i in range(len(temp)):
			if temp[i] == x:
				while len(stack):
					val = stack.pop()
					if val > int(x):
						count += 1
					else:
						stack.append(val)
						break
			if int(temp[i]) <= d:
				stack.append(int(temp[i]))
			else:
				count += 1
		temp = ''.join(map(str, stack)) + count * str(d)
	print(temp)
	t -= 1


for _ in range(int(input())):
	(n, d) = input().split()
	s = list(n)
	l = list(n)
	prev = d
	k = 0
	for x in range(len(l) - 1, -1, -1):
		if n[x] > prev:
			s[x] = ''
			k += 1
		else:
			prev = s[x]
	s = ''.join(s) + d * k
	print(s)


t = int(input())
while t:
	ip = input().split()
	n = ip[0]
	d = int(ip[1])
	a = [int(i) for i in n]
	l = len(a)
	s = ''
	i = 0
	while i < l:
		mn = min(a[i:])
		if mn < d:
			cnt = a[i:].count(mn)
			first_idx = a[::-1].index(mn)
			i = l - 1 - first_idx + 1
			s += str(mn) * cnt
		else:
			break
	n = len(s)
	s += str(d) * (l - n)
	print(s)
	t = t - 1


import numpy as np
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	list3 = list(str(n))
	list3 = list(map(int, list3))
	list3.append(k)
	list3.remove(max(list3))
	list2 = []
	list2 = list3.copy()
	v = ()
	while True:
		(cnt, flag) = (0, 0)
		list2.append(k)
		for i in range(0, len(list2) - 1, 1):
			cnt += 1
			if list2[i] > list2[i + 1]:
				list2.remove(list2[i])
				flag = 1
				break
		if cnt == len(list2) - 1 and flag == 0:
			list2.remove(list2[cnt])
		v = tuple(np.array(list2) - np.array(list3))
		if all([val == 0 for val in v]):
			break
		list3 = list2.copy()
	for i in range(len(list2)):
		if int(list2[i]) != 0:
			print(''.join(map(str, list2[i:])))
			break


import sys
test = int(input())
sol = []
for i in range(test):
	j = list(map(int, input().strip().split(' ')))
	(n, d) = (j[0], j[1])
	digits = list(str(n))
	for i in range(len(digits) - 1, -1, -1):
		first = 0
		if i < len(digits) - 1:
			if int(digits[i]) > int(digits[i + 1]):
				first = 1
		if int(digits[i]) >= d or first == 1:
			digits.append(str(d))
			del digits[i]
	str1 = ''
	sol.append(str1.join(digits))
for i in range(test):
	print(int(sol[i]))


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	s = str(l[0])
	while 1:
		s = s + str(l[1])
		for x in range(len(s) - 1):
			if s[x] > s[x + 1]:
				s = s[:x] + s[x + 1:]
				break
		else:
			s = s[:len(s) - 1]
			break
	print(int(s))


t = int(input())
while t:
	t -= 1
	(n, d) = map(str, input().split())
	n = list(map(str, n))
	m = int(d)
	count = 0
	for i in range(len(n) - 1, -1, -1):
		if int(n[i]) > m:
			count += 1
			n[i] = ''
		elif int(n[i]) < m:
			m = int(n[i])
	print(''.join(n) + d * count)


t = int(input())
while t:
	(n, d) = input().split()
	min = int(d)
	N = list(n)
	count = 0
	for i in range(len(N) - 1, -1, -1):
		if int(N[i]) > min:
			N[i] = ''
			count += 1
		else:
			min = int(N[i])
	print(''.join(N) + d * count)
	t -= 1


t = int(input())
while t:
	t = t - 1
	(n, d) = input().split()
	n = list(n)
	d = int(d)
	n = list(map(int, n))
	x = []
	n.reverse()
	z = 0
	cc = d
	for c in n:
		if c > cc:
			z += 1
		else:
			x.append(c)
			cc = c
	x.reverse()
	for _ in range(z):
		x.append(d)
	x = list(map(str, x))
	print(''.join(x))


for ii in range(int(input())):
	(s, d) = map(str, input().split())
	l = list(s)
	a = [l[0]]
	for i in range(1, len(l)):
		if l[i] >= a[-1]:
			a.append(l[i])
		elif l[i] < a[-1]:
			while len(a) > 0 and a[-1] > l[i]:
				a = a[:len(a) - 1]
			a.append(l[i])
	c = 0
	for i in a:
		if i <= d:
			print(i, end='')
			c += 1
		else:
			break
	print(d * (len(l) - c))


t = int(input())
while t:
	(N, d) = [x for x in input().split()]
	a = [int(x) for x in N]
	d = int(d)
	n = len(a)
	i = 0
	s = ''
	while i < n:
		m = min(a[i:])
		if m < d:
			c = a[i:].count(m)
			i = len(a) - 1 - a[::-1].index(m)
			i = i + 1
			s = s + str(m) * c
		else:
			break
	ls = len(s)
	s = s + str(d) * (n - ls)
	print(s)
	t = t - 1


for _ in range(int(input())):
	(n, c) = [int(i) for i in input().split()]
	(lis, kk, res) = ([int(i) for i in str(n)], -1, [])
	for min1 in range(1, c + 1):
		for i in range(kk + 1, len(lis)):
			if lis[i] == min1:
				res.append(str(lis[i]))
				kk = i
	for i in range(len(lis) - len(res)):
		res.append(str(c))
	print(''.join(res))


import sys
SUPPRESS_DEBUG = False

def log(*args, sep=' ', end='\n'):
	if SUPPRESS_DEBUG:
		return
	print(*args, file=sys.stderr, sep=sep, end=end)
T = int(input())
for _ in range(T):
	log('Testcase:', _ + 1, 'of', T)
	(N, d) = input().strip().split(' ')
	log(N, d)
	smallest = min(N)
	largest = max(N)
	if d < smallest:
		print(d * len(N))
		continue
	count = 0
	for digit in range(int(d) + 1, 10):
		str_digit = str(digit)
		count += N.count(str_digit)
		N = N.replace(str_digit, '')
	log('Count:', count, 'N:', N)
	for digit in range(int(d), 0, -1):
		str_digit = str(digit)
		while True:
			try:
				left_most_index = N.index(str_digit)
			except ValueError:
				break
			if any(map(lambda x: str_digit > x, N[left_most_index + 1:])):
				count += 1
				N = N.replace(str_digit, '', 1)
				log('Knocked', str_digit, ':', N)
			else:
				break
	N += d * count
	print(N)
	log('')


for x in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(str(n))
	l1 = []
	y = 0
	t = 0
	while True:
		m = min(l)
		pos = l.index(m)
		if int(m) >= d:
			break
		else:
			l1.append(m)
		if pos + 1 >= len(l):
			break
		for x in range(pos + 1):
			l.remove(l[0])
	t1 = ''.join(l1)
	t1 = str(t1) + str(d) * (len(str(n)) - len(str(t1)))
	print(t1)


from sys import stdin, stdout
for _ in range(int(input())):
	(n, d) = map(str, stdin.readline().split())
	li = list(n)
	s = d
	c = 0
	for i in range(len(n) - 1, -1, -1):
		if li[i] > d:
			li[i] = ''
			c += 1
		else:
			d = li[i]
	s = ''.join(li) + c * s
	print(s)


t = int(input())
while t:
	t = t - 1
	s = input().split()
	n = list(map(int, s[0]))
	d = int(s[1])
	f = -1
	i = 0
	if n[len(n) - 1] > d:
		n[len(n) - 1] = d
	while i < len(n) - 1:
		f = -1
		if n[i] > n[i + 1]:
			f = i
		i += 1
		if f == -1:
			continue
		n.pop(f)
		n.append(d)
		i = 0
	print(''.join(map(str, n)))


t = int(input())
for _ in range(t):
	(n, d) = input().split(' ')
	q = int(d)
	k = []
	for i in n:
		k.append(i)
	k2 = k[:]
	min = int(d)
	for j in range(len(k2) - 1, -1, -1):
		if int(k2[j]) > min:
			k2.pop(j)
		else:
			min = int(k2[j])
	print(*k2, sep='', end='')
	print(d * (len(k) - len(k2)))


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(map(int, list(str(n))))
	if l == sorted(l):
		a = [x for x in l if x <= d]
		l = a + [d] * (len(l) - len(a))
	else:
		i = 0
		while True:
			if l[i] > l[i + 1]:
				l.pop(i)
				l.append(d)
				i = 0
			else:
				i += 1
			if l == sorted(l):
				break
	l = list(map(str, l))
	print(int(''.join(l)))


t = int(input())
for T in range(t):
	(n, d) = [x for x in input().split()]
	l = list(n)
	a = [l[0]]
	c = 0
	for i in range(1, len(l)):
		if l[i] >= a[-1]:
			a.append(l[i])
		else:
			while len(a) > 0 and a[-1] > l[i]:
				a = a[:len(a) - 1]
			a.append(l[i])
	for i in a:
		if i <= d:
			print(i, end='')
			c += 1
		else:
			break
	print(d * (len(l) - c))


t = int(input())
while t:
	(N, d) = input().split()
	N = list(N)
	minz = N.index(min(N))
	p = [min(N[minz], d)]
	count = minz
	for i in range(minz + 1, len(N)):
		while N[i] < p[-1]:
			count += 1
			p.pop()
		if N[i] < d:
			p.append(N[i])
		else:
			count += 1
	x = ''.join(p) + count * d
	print(x)
	t -= 1


t = int(input())
while t > 0:
	lst = input().split()
	n = list(lst[0])
	k = int(lst[1])
	original_len = len(n)
	count = 0
	min_var = int(n[0])
	ans = ''
	index = 0
	for i in range(len(n)):
		if int(n[i]) >= k:
			n[i] = -1
		elif min_var > int(n[i]):
			min_var = int(n[i])
			index = i
	i = 0
	while i < len(n):
		n[i] = int(n[i])
		i += 1
	i = index
	while i < len(n):
		min_sub_var = n[i]
		temp = i
		for j in range(i, len(n)):
			if n[j] != -1 and min_sub_var >= n[j]:
				min_sub_var = n[j]
				i = j
		rep_num = n[temp:].count(min_sub_var)
		dup_min_sub_var = min_sub_var
		min_sub_var = str(min_sub_var) * rep_num
		if min_sub_var != '-1' * rep_num:
			ans += str(min_sub_var)
		i += 1
	ans += str(k) * (original_len - len(ans))
	print(ans)
	t -= 1


t = int(input())
for _ in range(t):
	(N, d) = input().split()
	res = ''
	nonRemovableElementCount = 0
	nonRemovableMini = d
	for i in range(len(N) - 1, -1, -1):
		if N[i] <= nonRemovableMini:
			nonRemovableElementCount += 1
			res = N[i] + res
		if N[i] < nonRemovableMini:
			nonRemovableMini = N[i]
	print(res + d * (len(N) - nonRemovableElementCount))


for _ in range(int(input())):
	(N, d) = [int(x) for x in input().split()]
	S = str(N)
	New = str()
	List = []
	List1 = []
	for i in S:
		List.append(int(i))
	for i in range(len(List)):
		if List[i] == min(List[i:len(List)]):
			New += str(List[i])
	for i in New:
		List1.append(int(i))
	for i in range(len(List1) - 1, -1, -1):
		if List1[i] >= d:
			List1[i] = d
		else:
			break
	BadNew = str()
	for i in List1:
		BadNew += str(i)
	X = len(S) - len(BadNew)
	for i in range(X):
		BadNew += str(d)
	print(BadNew)


for t in range(int(input())):
	m = input().strip().split()
	n = m[0]
	d = m[1]
	l = len(n)
	g = l
	new = []
	while l != 0:
		mini = min(n)
		i = n.index(mini)
		n = n[i + 1:]
		if int(mini) < int(d):
			new.append(mini)
		l = len(n)
	nl = g - len(new)
	op = d * nl
	num = ''.join(new) + op
	print(int(num))


t = int(input())
while t:
	t -= 1
	(s, k) = input().split()
	n = len(s)
	(a, i) = (0, 0)
	stk = []
	while i < n:
		if s[i] >= k:
			a += 1
		elif stk == [] or stk[-1] <= s[i]:
			stk.append(s[i])
		else:
			stk.pop()
			i -= 1
			a += 1
		i += 1
	s = ''
	for i in stk:
		s += i
	print(s + a * k)


t = int(input())
for _ in range(t):
	(a, b) = input().split()
	d = {}
	for i in range(len(a)):
		try:
			d[a[i]] += [i]
		except:
			d[a[i]] = [i]
	x = list(d.keys())
	x.sort()
	c = -1
	ans = ''
	for i in x:
		if i > b:
			break
		for j in d[i]:
			if j > c:
				c = j
				ans += i
	print(ans + b * (len(a) - len(ans)))


def main():
	no_of_test = int(input())
	for test in range(no_of_test):
		(number, digit) = input().split()
		number_length = len(number)
		ans = ''
		index_of_min_ele = -1
		while index_of_min_ele < len(number):
			min_ele = min(number[index_of_min_ele + 1:])
			if min_ele >= digit:
				break
			min_ele_count = number[index_of_min_ele + 1:].count(min_ele)
			ans += min_ele * min_ele_count
			index_of_min_ele = number.rfind(min_ele)
			if index_of_min_ele == number_length - 1:
				break
		ans += digit * (number_length - len(ans))
		print(ans)
main()


for _ in range(int(input())):
	(n, d) = map(str, input().split())
	k = list(n)
	(dd, c, n) = (d, 0, len(n))
	for x in range(n):
		if int(k[n - x - 1]) > int(d):
			k.pop(n - x - 1)
			c += 1
		else:
			d = k[n - x - 1]
	print(''.join(k) + c * dd)


pk = int(input())
while pk > 0:
	(n, d) = input().split()
	a = list(map(int, n))
	mi = min(a)
	d = int(d)
	l = len(a)
	l1 = l
	if mi < d:
		last = l - a[::-1].index(mi) - 1
		m = 0
		while last < l:
			cmi = a.count(mi)
			for k in range(cmi):
				print(mi, end='')
				m = m + 1
			if last == l - 1:
				break
			a = a[last + 1:]
			mi = min(a)
			if mi >= d:
				break
			l = len(a)
			last = l - a[::-1].index(mi) - 1
		while m < l1:
			print(d, end='')
			m = m + 1
	else:
		for i in range(l1):
			print(d, end='')
	print()
	pk = pk - 1


t = int(input())
for i in range(t):
	(x, y) = input().split()
	d = int(y)
	p = list(x)
	n = [int(k) for k in p]
	q = n
	l = min(n)
	if l >= d:
		print(str(d) * len(n))
	else:
		count = 0
		for j in range(len(n)):
			if n[j] > l:
				count = count + 1
			elif n[j] == l:
				print(n[j], end='')
				q = n[j + 1:]
				if q == []:
					break
				l = min(q)
				if l >= d:
					count = count + len(q)
					break
		print(str(d) * count)


t = int(input())
for i in range(t):
	a = input().split()
	n = a[0]
	m = n
	d = a[1]
	s = ''
	i = 0
	while n != '':
		if min(n) < d:
			s = s + min(n)
		else:
			s = s + d
		n = n[n.index(min(n)) + 1:]
	for i in range(len(m) - len(s)):
		s = s + d
	print(s)


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	e = str(n)
	w = e[::-1]
	r = ''
	s = d
	for i in range(len(e)):
		if int(w[i]) <= s:
			r = r + w[i]
			s = int(w[i])
		else:
			r = str(d) + r
	print(r[::-1])


for _ in range(int(input())):
	(s, d) = input().split()
	a = list(s)
	ans = ''
	while len(a) != 0 and min(a) < d:
		ans += min(a)
		a = a[a.index(min(a)) + 1:]
	print(ans + d * (len(s) - len(ans)))


def solve(num, d):
	if int(num[len(num) - 1]) > d:
		num = num[0:len(num) - 1] + str(d)
	i = 0
	while i < len(num) - 1:
		if int(num[i]) > int(num[i + 1]):
			num = num[0:i] + num[i + 1:len(num)] + str(d)
			i = -1
		i += 1
	return num
t = int(input())
for j in range(t):
	(n, d) = map(int, input().split())
	print(solve(str(n), d))


for i in range(int(input())):
	(n, d) = input().split()
	n = list(n)
	x = int(d)
	y = n.copy()
	for j in range(len(n) - 1, -1, -1):
		if int(y[j]) <= x:
			x = int(y[j])
		else:
			y.pop(j)
	l = len(y)
	for k in range(len(n) - l):
		y.append(d)
	print(''.join(y))


t = int(input())
while t:
	(n, d) = [int(x) for x in input().split()]
	ans = 0
	if n == 1:
		ans = d if n > d else n
		print(ans)
	else:
		temp = str(n)
		l = len(temp)
		orig = temp[l - 1]
		if int(orig) > d:
			updat = str(d)
		else:
			updat = orig
		orig = updat
		for i in range(l - 2, -1, -1):
			orig = temp[i] + updat
			updat = updat + str(d)
			if int(orig) > int(updat):
				orig = updat
			else:
				updat = orig
		print(int(orig))
	t -= 1


t = int(input())
while t:
	t = t - 1
	(n, d) = list(map(int, input().split()))
	n = list(map(int, list(str(n))))
	n = n[::-1]
	new = []
	count = 0
	m = d
	for i in range(len(n)):
		if n[i] <= m:
			m = n[i]
			new.append(str(n[i]))
		else:
			count += 1
	new = new[::-1]
	for i in range(count):
		new.append(str(d))
	print(''.join(new))


t = int(input())
for _ in range(t):
	(n, k) = map(str, input().split())
	ans = ''
	for i in n:
		if int(i) < int(k):
			ans += i
	ans += k * (len(n) - len(ans))
	ka = list(map(int, list(ans)))
	d = min(ka)
	boo = []
	for i in range(len(ka)):
		if ka[i] == d:
			boo.append(i)
	count = 0
	for i in range(boo[-1]):
		if ka[i] != d:
			ka[i] = ''
			count += 1
	ka = list(map(str, list(ka)))
	for i in range(len(ka)):
		for j in range(i + 1, len(ka)):
			if ka[i] != '' and ka[j] != '':
				if int(ka[i]) > int(ka[j]):
					ka[i] = ''
					count += 1
					break
	ka += k * count
	c = ''.join(ka)
	print(c)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(str(n))
	a1 = list(map(int, a))
	x = m
	s = a1
	for i in range(len(a) - 1, -1, -1):
		if a1[i] <= x:
			x = a1[i]
		else:
			s.pop(i)
	l = len(s)
	for _ in range(len(a) - l):
		s.append(m)
	ans = int(''.join(map(str, s)))
	print(ans)


t = int(input())
while t > 0:
	(n, d) = list(map(str, input().strip().split()))
	if d <= min(n):
		print(d * len(n))
	else:
		if n[len(n) - 1] > d:
			n = n[:len(n) - 1] + d
		s = n
		m = min(n)
		for i in range(len(n) - 1):
			if n[i] > m:
				s = s.replace(n[i], '', 1) + d
			elif n[i] == m:
				m = min(n[i + 1:])
		print(s)
	t -= 1


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	n = str(n)
	greater = 0
	digits = []
	p = d
	for i in n[::-1]:
		if int(i) > p:
			greater += 1
		else:
			digits = [int(i)] + digits
			p = int(i)
	digits = digits + [d] * greater
	print(''.join((str(x) for x in digits)))


t = int(input())
while t:
	(n, d) = input().split()
	n = int(n)
	d = int(d)
	arr = []
	temp = n
	while n:
		arr.append(n % 10)
		n = n // 10
	arr = arr[::-1]
	len_arr = len(arr)
	i = 0
	while i != len_arr - 1:
		if arr[i] > arr[i + 1] or arr[i] > d:
			for j in range(i, len_arr - 1):
				arr[j] = arr[j + 1]
			arr[len_arr - 1] = d
			i = -1
		i = i + 1
	if arr[len_arr - 1] > d:
		arr[len_arr - 1] = d
	for i in range(len_arr):
		arr[i] = str(arr[i])
	string = ''.join(arr)
	print(int(string))
	t = t - 1