{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Beads of N colors are connected together into a circular necklace of N beads (N\u0026lt;\u003d1000000000). Your job is to calculate how many different kinds of the necklace can be produced. You should know that the necklace might not use up all the N colors, and the repetitions that are produced by rotation around the center of the circular necklace are all neglected. \r\u003cbr\u003e\r\u003cbr\u003eYou only need to output the answer module a given number P.\r\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input is an integer X (X \u0026lt;\u003d 3500) representing the number of test cases. The following X lines each contains two numbers N and P (1 \u0026lt;\u003d N \u0026lt;\u003d 1000000000, 1 \u0026lt;\u003d P \u0026lt;\u003d 30000), representing a test case."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one line containing the answer."}},{"title":"Sample","value":{"format":"HTML","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\r\n1 30000\r\n2 30000\r\n3 30000\r\n4 30000\r\n5 30000\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n3\r\n11\r\n70\r\n629\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}