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.

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 $ ).

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