「CZOI-R1」进制

你有一个数 $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$。