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


\(ans=\sum_{L|n}n^{L-1} \phi(n/L)\),求这个式子的值。。。枚举L,根号n求欧拉函数,由于n的约数个数远小于\(\sqrt n\),求欧拉函数可以枚举质数。。。所以实际上还是很快的