2642. HeHe

单点时限: 2.0 sec

内存限制: 256 MB

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.

输入格式

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.

输出格式

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

样例

Input
1
2 3
Output
2

1 人解决,1 人已尝试。

2 份提交通过,共有 5 份提交。

9.3 EMB 奖励。

创建: 11 年前.

修改: 2 年,11 月前.

最后提交: 11 年前.

来源: 多校联合比赛BNU站

题目标签