Beads of N colors are connected together into a circular necklace of N beads (N<=1000000000). 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. 

You only need to output the answer module a given number P. 


The first line of the input is an integer X (X <= 3500) representing the number of test cases. The following X lines each contains two numbers N and P (1 <= N <= 1000000000, 1 <= P <= 30000), representing a test case.


For each test case, output one line containing the answer.

Sample Input

Sample Output


POJ Monthly,Lou Tiancheng
那么算出欧拉函数可以在sqrt的时间内解决 另外这题取模了 因此不可以把答案都算出来之后整体/n 应该在计算的时候算n^(n-1)即可



退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下