# Click Here!

It is a complicated version of problem F1. The difference between them is the constraints (F1: k2k≤2, F2: k10k≤10).

You are given an integer nn. Find the minimum integer xx such that xnx≥n and the number xx is kkbeautiful.

A number is called kkbeautiful if its decimal representation having no leading zeroes contains no more than kk different digits. E.g. if k=2k=2, the numbers 343444334344435555055550777777 and 2121 are kkbeautiful whereas the numbers 120120445435445435 and 998244353998244353 are not.

Input Nearest Beautiful Number (hard version) solution codeforces

The first line contains one integer tt (1t1041≤t≤104) — the number of test cases. Then tt test cases follow.

Each test case consists of one line containing two integers nn and kk (1n1091≤n≤1091k101≤k≤10).

Output

For each test case output on a separate line xx — the minimum kkbeautiful integer such that xnx≥n.

Example
input

Copy
6
2021 3
177890 2
34512 3
724533 4
998244353 1
12345678 10

output

Copy
2021
181111
34533
724542
999999999
12345678