Это усложнённая версия задачи 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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач