题目描述

小 $\delta$ 喜欢转圈圈。

他有一个圈，被均匀分成了 $n$ 个格子，神奇的是，$n$ 是一个质数。第 $i$ 个格子上写着一个数 $i \times m$，他现在站在第一个格子上。

接下来他会看看脚下踩着的数是多少，然后向前走这么多格。他会一直反复这么做。

求最终被小 $\delta$ 踩到过的格子的数量。由于小 $\delta$ 有很多圈圈，所以他会问你很多次。

输入格式

第一行包含一个正整数 $T$，代表询问次数。

对于每组询问，输入一行两个正整数 $n,m$。

输出格式

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

6
5 2
11 10
17 12
23 8
31 12
9999901 114514

4
2
4
11
30
16260

提示

【样例解释】

以第一次询问为例，小 $\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$ 是质数。