You are given a positive integer $x$.

You can apply the following operation to the number: remove one occurrence of any digit in such a way that the resulting number does not contain any leading zeroes and is still a positive integer. For example, $10142$ can be converted to $1142$, $1042$, $1012$ or $1014$ (note that $0142$ is not a valid outcome); $10$ can be converted to $1$ (but not to $0$ since it is not positive).

Your task is to find the minimum positive integer that you can obtain from $x$ if you can apply the aforementioned operation exactly $k$ times.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases.

The first line of each test case contains a single integer $x$ ($1 \le x < 10^{500000}$).

The second line contains a single integer $k$ ($0 \le k < |x|$), where $|x|$ is the length of the number $x$.

The sum of $|x|$ over all test cases does not exceed $5 \cdot 10^5$.


-----Output-----

For each test case, print one integer — the minimum positive number that you can obtain from $x$ if you can apply the operation exactly $k$ times.


-----Examples-----

Input
5
10000
4
1337
0
987654321
6
66837494128
5
7808652
3
Output
1
1337
321
344128
7052


-----Note-----

None

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from dataclasses import dataclass
from time import time
import math

@dataclass
class MyInput:
	t: int
	test_cases: list

def get_input():
	t = int(input())
	test_cases = []
	for _ in range(t):
		x = input()
		k = input()
		test_cases.append((x, k))
	return MyInput(t=t, test_cases=test_cases)

def get_sample_idx_first(x, k):
	(_, min_idx) = min(((val, idx) for (idx, val) in enumerate(x[:k + 1]) if val != '0'))
	return min_idx

def resolve(x, k):
	if k == 0:
		return x
	ret = []
	min_value_idx = get_sample_idx_first(x, k)
	ret.append(x[min_value_idx])
	k = k - min_value_idx
	for i in range(min_value_idx + 1, len(x)):
		while len(ret) > 1 and k and (ret[-1] > x[i]):
			ret.pop()
			k -= 1
		ret.append(x[i])
	while len(ret) > 1 and k:
		ret.pop()
		k -= 1
	return ''.join(ret)

def main():
	myinput = get_input()
	for i in range(myinput.t):
		(x, k) = myinput.test_cases[i]
		k = int(k)
		print(resolve(x, k))
	return myinput
main()


import bisect

def rem(ss, kk):
	ret = []
	for c in ss:
		while len(ret) > 0 and kk and (ret[-1] > c):
			ret.pop()
			kk -= 1
		ret.append(c)
	while len(ret) > 0 and kk:
		ret.pop()
		kk -= 1
	return ''.join(ret)
t = int(input())
for tc in range(t):
	s = input()
	n = len(s)
	k = int(input())
	i = 0
	m = s[0]
	for j in range(1, k + 1):
		if '0' < s[j] < m:
			m = s[j]
			i = j
	print(m + rem(s[i + 1:], k - i))


def restofs(s, k):
	lst = []
	for i in s:
		while len(lst) > 0 and k != 0 and (lst[-1] > i):
			lst.pop()
			k -= 1
		lst.append(i)
	while len(lst) > 0 and k != 0:
		lst.pop()
		k -= 1
	return ''.join(lst)
for __ in range(int(input())):
	s = input()
	k = int(input())
	(i, x) = (0, s[0])
	for j in range(1, k + 1):
		if s[j] > '0' and s[j] < x:
			x = s[j]
			i = j
	print(x + restofs(s[i + 1:], k - i))


def allsmall(l, k):
	n = len(l)
	res = [l[0]]
	z = 0
	i = 1
	t = 0
	last = l[0]
	while i < n and t < k:
		if z == len(res) - 1 and last > l[i] and (l[i] != '0'):
			if k - t >= z + 1:
				res = []
				t += z + 1
				z = 0
				res.append(l[i])
				last = res[0]
				i += 1
				continue
		if res[-1] > l[i]:
			if l[i] == '0' and len(res) == 1:
				res.append(l[i])
				z += 1
				i += 1
			elif k - t >= 1:
				res.pop()
				t += 1
			else:
				break
		else:
			if l[i] == '0':
				z += 1
			res.append(l[i])
			i += 1
		if len(res) == 0:
			res.append(l[i])
			i += 1
		last = res[0]
	res.extend(l[i:n])
	res = res[0:n - k]
	s = ''
	for i in res:
		s += f'{i}'
	return s
t = int(input())
for i in range(t):
	l = input()
	k = int(input())
	print(allsmall(l, k))


t = int(input())
for i in range(t):
	x = input()
	k = int(input())
	a = len(x)
	count = '99999999999999999999999999999999999999999999990'
	b = 0
	for d in range(k + 1):
		if x[d] < count and x[d] != '0':
			count = x[d]
			b = d
	k -= b
	nums = []
	d = k
	for e in range(b + 1, a):
		while nums and nums[-1] > x[e]:
			if k > 0:
				nums.pop()
				k -= 1
			else:
				break
		nums.append(x[e])
	print(count + ''.join(nums[:len(nums) - k]))


iterations = int(input())
for _ in range(iterations):
	number_string = input()
	number_of_operations = int(input())
	(minimum, index) = (number_string[0], 0)
	for i in range(number_of_operations + 1):
		if '0' < number_string[i] < minimum:
			(minimum, index) = (number_string[i], i)
	output_string = number_string[index]
	number_string = number_string[index + 1:]
	number_of_operations -= index
	remaining_output = []
	for number in number_string:
		while len(remaining_output) > 0 and number_of_operations > 0 and (remaining_output[-1] > number):
			remaining_output.pop()
			number_of_operations -= 1
		remaining_output.append(number)
	output_string += ''.join(remaining_output[:len(remaining_output) - number_of_operations])
	print(output_string)


from math import *
from heapq import heappop, heappush
MOD = 10 ** 9 + 7

class Solution:
	pass

def solution():
	line = input()
	k = int(input())
	m = len(line) - k
	if k == 0:
		return print(line)
	res = []
	min_index = -1
	min_val = inf
	m -= 1
	for i in range(len(line) - m):
		val = int(line[i])
		if val > 0 and val < min_val:
			min_val = val
			min_index = i
	if min_val >= inf:
		return print(0)
	res = [min_val]
	min_heap = []
	for i in range(min_index + 1, len(line)):
		val = (int(line[i]), i)
		heappush(min_heap, val)
		num_left_vals = len(line) - i - 1
		if num_left_vals == m - 1:
			while min_heap and min_heap[0][1] < min_index:
				heappop(min_heap)
			(val, min_index) = heappop(min_heap)
			res.append(val)
			m -= 1
	return print(''.join(map(str, res)))

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		solution()
import sys
import threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(1 << 27)
thread = threading.Thread(target=main)
thread.start()
thread.join()


from bisect import bisect_left
from collections import defaultdict

def case():
	x = input()
	k = int(input())
	pos = defaultdict(list)
	for i in range(len(x) - 1, -1, -1):
		pos[x[i]].append(i)
	ans = []
	i = 0
	target = len(x) - k
	while i < len(x):
		if len(ans) == target:
			break
		for goal in '0123456789':
			if i == 0 and goal == '0':
				continue
			if not pos[goal]:
				continue
			while pos[goal] and pos[goal][-1] < i:
				pos[goal].pop()
			if pos[goal]:
				cut_til = pos[goal][-1]
				if cut_til - i <= k:
					k -= cut_til - i
					i = cut_til
					ans.append(x[i])
					break
		i += 1
	print(''.join(ans))

def go():
	t = int(input())
	for i in range(t):
		case()
go()