CF1560F2.Nearest Beautiful Number (hard version)

It is a complicated version of problem F1. The difference between them is the constraints (F1: $k \le 2$, F2: $k \le 10$).

You are given an integer $n$. Find the minimum integer $x$ such that $x \ge n$ and the number $x$ is $k$-beautiful.

A number is called $k$-beautiful if its decimal representation having no leading zeroes contains no more than $k$ different digits. E.g. if $k = 2$, the numbers $3434443$, $55550$, $777$ and $21$ are $k$-beautiful whereas the numbers $120$, $445435$ and $998244353$ are not.

这是问题 F1 的一个复杂版本。它们之间的区别在于约束条件（F1：$k \le 2$，F2：$k \le 10$）。

给你一个整数 $n$。请找出最小的整数 $x$，使得 $x \ge n$ 且 $x$ 是 $k$-beautiful 的。

若一个数的十进制表示（不含前导零）中至多包含 $k$ 个不同的数字，则称该数为 $k$-beautiful。例如，当 $k = 2$ 时，数字 $3434443$、$55550$、$777$ 和 $21$ 是 $k$-beautiful 的，而数字 $120$、$445435$ 和 $998244353$ 则不是。

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case consists of one line containing two integers $n$ and $k$ ($1 \le n \le 10^9$, $1 \le k \le 10$).

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

每个测试用例由一行组成，包含两个整数 $n$ 和 $k$（$1 \le n \le 10^9$，$1 \le k \le 10$）。

For each test case output on a separate line $x$ — the minimum $k$-beautiful integer such that $x \ge n$.

对于每个测试用例，在单独一行输出 $x$ —— 满足 $x \ge n$ 的最小 $k$-beautiful 整数。