这是问题 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