← 返回题目列表

Codeforces · 1765/N

N. 数量减少

中文机器翻译题面 查看原题

给你一个正整数 $$$x$$$。

您可以对数字应用以下操作:删除出现的任何数字,使结果数字不包含任何前导零并且仍然是正整数。例如,$$$10142$$$ 可以转换为 $$$1142$$$、$$$1042$$$、$$$1012$$$ 或 $$$1014$$$(请注意,$$$0142$$$ 不是有效结果); $$$10$$$ 可以转换为 $$$1$$$ (但不能转换为 $$$0$$$,因为它不是正数)。

你的任务是找到从 $$$x$$$ 中获得的最小正整数,如果你能精确地应用上述操作 $$$k$$$ 次。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$x$$$ ($$$1 \le x < 10^{500000}$$$)。

第二行包含一个整数 $$$k$$$ ($$$0 \le k < |x|$$$),其中 $$$|x|$$$ 是数字 $$$x$$$ 的长度。

所有测试用例的 $$$|x|$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 如果您可以精确应用操作 $$$k$$$ 次,则可以从 $$$x$$$ 获得的最小正数。

示例

输入 #1

5
10000
4
1337
0
987654321
6
66837494128
5
7808652
3

输出 #1

1
1337
321
344128
7052