F2. Ближайшее красивое число (усложнённая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это усложнённая версия задачи 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$$$.

Пример
Входные данные
6
2021 3
177890 2
34512 3
724533 4
998244353 1
12345678 10
Выходные данные
2021
181111
34533
724542
999999999
12345678