D. Polycarp and Div 3

 F2. Nearest Beautiful Number (hard version)

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

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

Input

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

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

Output

For each test case output on a separate line x$x$ — the minimum k$k$-beautiful integer such that x≥n$x\ge 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