该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

前面忘了，后面忘了

时间限制：1s

空间限制：256MB

题目描述

小李老师给班上的 $n$ 个同学每人买了 $n^{m-1}$ 苹果，一共 $n^m$ 个苹果。

他将这些苹果一个一个依次发给每个同学，经过若干轮之后，他从剩下的苹果中拿出一个给了最后一个同学，此时他发现还剩下一个苹果。

小李老师意识到，有人并没有来上课；不过只需要知道每人拿了多少苹果，就可以知道有多少人缺席了，小李老师这样想。

但是遗憾的是，小李老师忘了给每个人发的苹果数量，所以小李老师只能在课后来求助你，你能根据现有数据算出当时班上可能有多少人吗？

用数学符号描述，即你需要找到一个值 $k$ 使得以下式子成立：

输入格式

第一行一个整数 $T$，代表测试数据组数。

接下来 $T$ 行，每行两个整数 $n$ 和 $m$，用空格隔开，含义见描述。

输入保证有解。

输出格式

对于每组测试数据，输出一个整数 $k$ ($1 < k < n$)，代表当时班上可能的人数，占一行。

如果有多个满足条件的答案，只需要输出其中一个即可。

样例输入

3
5 3
8 2
7 2

样例输出

2
3
4

样例解释

对于第一组测试数据，$5^3\%2=125\%2=1$；

对于第二组测试数据，$8^2\%3=64\%3=1$；

对于第三组测试数据，$7^2\%4=49\%4=1$。

数据范围与约定

对于 $50\%$ 的数据，$3 \le n \le 10$，$2 \le m \le 10$；

对于 $100\%$ 的数据，$1 \le T \le 10^5$，$3 \le n \le 10^9$，$2 \le m \le 10^9$。

注意输出的值不能为 $1$ ，也不能超过或等于 $n$ 的值。

—— “为什么不直接看每个人拿了多少个苹果？”

—— “我忘了...”