K-Balanced Number

A decimal number is written using only the digits 0 through 9.

For a positive integer $N$, look at the digits used to write $N$ in decimal, where $N$ does not start with 0. If the count of the most frequently used digit minus the count of the least frequently used digit is at most $K$, then $N$ is called a $K$-balanced number.

Given positive integers $X$ and $K$, find the largest $K$-balanced number that is less than or equal to $X$.

The first line contains the number of test cases $T$. $(1 \leq T \leq 10^5)$

Each of the next $T$ lines contains positive integers $X$ and $K$, separated by a space. $(1 \leq X < 10^{10^5}, 1 \leq K \leq 10^5)$

In all test cases, the sum of the lengths of $X$ is at most $10^5$.

For each test case, print the answer on its own line, in input order.

• The input and output can exceed the range of a 64-bit integer.
• Digits that are not used are not counted.
• Python users are recommended to submit with PyPy.