P10515 转圈

小 $\delta$ 喜欢转圈圈。 他有一个圈，被均匀分成了 $n$ 个格子，神奇的是，$n$ 是一个质数。第 $i$ 个格子上写着一个数 $i \times m$，他现在站在第一个格子上。 接下来他会看看脚下踩着的数是多少，然后向前走这么多格。他会一直反复这么做。 求最终被小 $\delta$ 踩到过的格子的数量。由于小 $\delta$ 有很多圈圈，所以他会问你很多次。

第一行包含一个正整数 $T$，代表询问次数。 对于每组询问，输入一行两个正整数 $n,m$。

对于每次询问，输出一行一个正整数，代表被踩到的格子的数量。

**【样例解释】** 以第一次询问为例，小 $\delta$ 依次经过的格子编号为 $1 \to 3 \to 4 \to 2 \to 1 \to \cdots$，因此被踩到过的格子个数为 $4$。 **【数据范围】** - 对于 $20\%$ 的数据，$n \le 10^3$，$T \le 2 \times 10^3$。 - 对于另外 $40\%$ 的数据，$T \le 3 \times 10^3$。 - 对于另外 $40\%$ 的数据，无特殊性质。 对于所有数据，$1 \le m < n \le 10^7$，$1 \le T \le 4 \times 10^5$。保证 $n$ 是质数。