{"raw_statement":[{"iden":"statement","content":"小 $\\delta$ 喜欢转圈圈。\n\n他有一个圈，被均匀分成了 $n$ 个格子，神奇的是，$n$ 是一个质数。第 $i$ 个格子上写着一个数 $i \\times m$，他现在站在第一个格子上。\n\n接下来他会看看脚下踩着的数是多少，然后向前走这么多格。他会一直反复这么做。\n\n求最终被小 $\\delta$ 踩到过的格子的数量。由于小 $\\delta$ 有很多圈圈，所以他会问你很多次。"},{"iden":"input","content":"第一行包含一个正整数 $T$，代表询问次数。\n\n对于每组询问，输入一行两个正整数 $n,m$。"},{"iden":"output","content":"对于每次询问，输出一行一个正整数，代表被踩到的格子的数量。"},{"iden":"note","content":"**【样例解释】**\n\n以第一次询问为例，小 $\\delta$ 依次经过的格子编号为 $1 \\to 3 \\to 4 \\to 2 \\to 1 \\to \\cdots$，因此被踩到过的格子个数为 $4$。\n\n**【数据范围】**\n\n- 对于 $20\\%$ 的数据，$n \\le 10^3$，$T \\le 2 \\times 10^3$。\n- 对于另外 $40\\%$ 的数据，$T \\le 3 \\times 10^3$。\n- 对于另外 $40\\%$ 的数据，无特殊性质。\n\n对于所有数据，$1 \\le m < n \\le 10^7$，$1 \\le T \\le 4 \\times 10^5$。保证 $n$ 是质数。\n"}],"translated_statement":null,"sample_group":[["6\n5 2\n11 10\n17 12\n23 8\n31 12\n9999901 114514","4\n2\n4\n11\n30\n16260"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}