HeHe

Time Limit: 1000ms
Memory Limit: 65535KB
This problem will be judged on HDU. Original ID: 2879
64-bit integer IO format: %I64d      Java class name: Main

Description

In the equation X^2≡X(mod N) where x∈[0,N-1], we define He[N] as the number of solutions.
And furthermore, define HeHe[N]=He[1]*……*He[N]
Now here is the problem, write a program, output HeHe[N] modulo M for a given pair N, M.

Input

First line: an integer t, representing t test cases.
Each test case contains two numbers N (1<=N<=10^7) and M (0<M<=10^9) separated by a space.

Output

For each test case, output one line, including one integer: HeHe[N] mod m.

Sample Input

1
2 3

Sample Output

2

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .