← 返回题目列表

Codeforces · 1560/F2

F2. 最近的美丽数字(硬版)

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

这是问题 F1 的复杂版本。它们之间的区别在于约束(F1:$$$k \le 2$$$,F2:$$$k \le 10$$$)。

给你一个整数$$$n$$$。找到最小整数 $$$x$$$ 使得 $$$x \ge n$$$ 并且数字 $$$x$$$ 是 $$$k$$$-美丽的。

如果一个数字没有前导零,其十进制表示形式包含的不同数字不超过 $$$k$$$,则该数字被称为 $$$k$$$ 美丽。例如。如果 $$$k = 2$$$,则数字 $$$3434443$$$、$$$55550$$$、$$$777$$$ 和 $$$21$$$ 是 $$$k$$$ 美丽的,而数字 $$$120$$$、$$$445435$$$ 和 $$$998244353$$$ 则不是。

输入

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

每个测试用例由一行组成,其中包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le k \le 10$$$)。

输出

对于每个测试用例在单独的行上输出 $$$x$$$ — 最小的 $$$k$$$ 美丽整数,使得 $$$x \ge n$$$。

示例

输入 #1

6
2021 3
177890 2
34512 3
724533 4
998244353 1
12345678 10

输出 #1

2021
181111
34533
724542
999999999
12345678