题目描述

你有一个数 $x$，你需要对它进行 $n$ 次操作。

每次操作，你可以选择 $y$ 进制下的数 $x$ 的某一个有效位上数值增加 $1$。
第一个非零数位及其后面的数位是有效位。

注意：

• 对于每次操作，你可以任意取 $y\in[2,+\infty)$；
• 你需保证增加操作不会使 $y$ 进制下的数 $x$ 产生进位。

现在你需要求 $n$ 次操作后这个数最大是多少。

答案以十进制输出，并对 $10^9+7$ 取模。你需要输出的是这个数的最大值对 $10^9+7$ 取模的结果，而并非对 $10^9+7$ 取模后的最大值。

输入格式

本题有多组测试数据。

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行两个整数 $x,n$，分别表示初始数字、操作次数。

输出格式

对于每组测试数据，输出一行一个整数，表示 $x$ 进行 $n$ 次操作后的最大值。

1
2 1

3

提示

【样例解释】

很明显，$2$ 在二进制时为 $10$，在三或更高进制时为 $2$。

二进制时，在第一位 $+1$ 会导致二进制产生进位，只能在第二位 $+1$，此时得到的结果为 $11$，转换为十进制为 $3$。

在三或更高进制时，只能往末位 $+1$，三进制下会产生进位，舍去。四或更高进制时得到结果均为 $3$，转化为十进制的结果也是 $3$。

【数据范围】

本题采用捆绑测试。

• Subtask #1（$20\text{ pts}$）：$x\le 2$。
• Subtask #2（$20\text{ pts}$）：$n=1$。
• Subtask #3（$60\text{ pts}$）：无特殊限制。

对于 $100\%$ 的数据，$1\le x,n\le10^9$，$1\le T\le10^6$。