SP20562 TANDC - Tracy and Charlie

Tracy 开发了一种名为 N-Cube 的数学游戏来教授 Charlie，这个游戏主要是围绕数字 N。首先，Tracy 给 Charlie 一个数字 $N$，Charlie 然后列出所有整数的 $N$ 次幂，并按升序排列（例如 $1^N, 2^N, 3^N, \ldots$）。这个过程旨在教授 Charlie 幂运算。 接下来，Charlie 进行如下的减法游戏，共进行 $N$ 次：对于列表中的每一对连续数字，计算它们的差值。这些差值将构成下次迭代的新列表。例如，如果 $N$ 是 6，列表从 $[1, 64, 729, 4096, \ldots]$ 变为 $[63, 685, 3367, \ldots]$，再进行 5 次这样的操作。完成减法游戏后，Charlie 需要准确告诉 Tracy 当前列表中的第 $N$ 个元素。这个数就是游戏的「价值」。 经过不断练习，Charlie 掌握了这个游戏。为提升难度，Tracy 决定给 Charlie 两个数 **M**（其中 $M$ 是素数）和 **R**，而不是单一的数字 $N$。现在，游戏将从 $M^R - 1$ 开始一个新的列表。由于这个游戏的「价值」可能非常大，Charlie 只需要找出最大整数 $K$ 使得 $M^K$ 整除该数。由于 $K$ 也可能很庞大，你需要输出 $K$ 对 $1000000007$（即 $10^9 + 7$）取模的结果。

第一行输入一个整数 $T$，表示测试用例的数量。接下来的每一行包含两个整数 $M$ 和 $R$，分别代表每个测试用例的参数。

对于每个测试用例，输出 Charlie 计算出的结果，即整除次数的最大值 $K$ 模 $1000000007$ 后的结果。

- $1 \leq T \leq 1000$ - $2 \leq M \leq 10^9$ - $1 \leq R \leq 10^9$ - $M$ 是一个素数。 **本翻译由 AI 自动生成**