Problem Description

You have a number $x$, and you need to perform $n$ operations on it.

In each operation, you may choose one valid digit of $x$ in base $y$ and increase its value by $1$.
The first non-zero digit and all digits after it are considered valid digits.

Note:

• For each operation, you may choose any $y\in[2,+\infty)$.
• You must ensure that the increment does not cause a carry in the base-$y$ representation of $x$.

Now you need to find the maximum possible value of this number after $n$ operations.

Output the answer in decimal, modulo $10^9+7$. You need to output the result of (the maximum value) modulo $10^9+7$, not the maximum value after taking modulo $10^9+7$.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

The next $T$ lines each contain two integers $x,n$, representing the initial number and the number of operations.

Output Format

For each test case, output one integer per line, representing the maximum value of $x$ after performing $n$ operations.

1
2 1

3

Hint

[Sample Explanation]

Clearly, $2$ is $10$ in binary, and it is $2$ in base $3$ or higher.

In binary, adding $1$ to the first digit would cause a carry, so you can only add $1$ to the second digit. The result is $11$, which is $3$ in decimal.

In base $3$ or higher, you can only add $1$ to the last digit. In base $3$ it would cause a carry, so discard it. In base $4$ or higher, the result is always $3$, and the converted decimal result is also $3$.

[Constraints]

This problem uses bundled testdata.

• Subtask #1 ($20\text{ pts}$): $x\le 2$.
• Subtask #2 ($20\text{ pts}$): $n=1$.
• Subtask #3 ($60\text{ pts}$): no special constraints.

For $100\%$ of the testdata, $1\le x,n\le10^9$, and $1\le T\le10^6$.

Translated by ChatGPT 5