{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"$N$ 种颜色的珠子连接在一起,形成 $N$ 颗珠子的圆形项链。求有多少本质不同的项链。项链可能不会用完所有的 $N$ 种颜色,这里本质不同指旋转后不相同。\n\n输出模 $P$ 的方案数。"}},{"title":"输入","value":{"format":"MD","content":"第一行是一个整数 $X$ ($X \\le 3500$),表示测试用例的数量。\n以下 $X$ 行分别包含两个数字 $N$ 和 $P$($1 \\le N \\le 10^9,1 \\le P \\le 30000$),表示一个测试用例。"}},{"title":"输出","value":{"format":"MD","content":"对于每个测试用例,输出一行一个整数。"}},{"title":"样例","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1 30000\n2 30000\n3 30000\n4 30000\n5 30000\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n3\n11\n70\n629\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}