{"problem":{"name":"转圈","description":{"content":"小 $\\delta$ 喜欢转圈圈。 他有一个圈，被均匀分成了 $n$ 个格子，神奇的是，$n$ 是一个质数。第 $i$ 个格子上写着一个数 $i \\times m$，他现在站在第一个格子上。 接下来他会看看脚下踩着的数是多少，然后向前走这么多格。他会一直反复这么做。 求最终被小 $\\delta$ 踩到过的格子的数量。由于小 $\\delta$ 有很多圈圈，所以他会问你很多次。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10515"},"statements":[{"statement_type":"Markdown","content":"小 $\\delta$ 喜欢转圈圈。\n\n他有一个圈，被均匀分成了 $n$ 个格子，神奇的是，$n$ 是一个质数。第 $i$ 个格子上写着一个数 $i \\times m$，他现在站在第一个格子上。\n\n接下来他会看看脚下踩着的数是多少，然后向前走这么多格。他会一直反复这么做。\n\n求最终被小 $\\delta$ 踩到过的格子的数量。由于小 $\\delta$ 有很多圈圈，所以他会问你很多次。\n\n## Input\n\n第一行包含一个正整数 $T$，代表询问次数。\n\n对于每组询问，输入一行两个正整数 $n,m$。\n\n## Output\n\n对于每次询问，输出一行一个正整数，代表被踩到的格子的数量。\n\n[samples]\n\n## Note\n\n**【样例解释】**\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$ 是质数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10515","tags":["原根","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["6\n5 2\n11 10\n17 12\n23 8\n31 12\n9999901 114514","4\n2\n4\n11\n30\n16260"]],"created_at":"2026-03-03 11:09:25"}}