Problem Description

For given positive integer $n$, suppose that $p_1 = 2 < p_2 = 3 < \cdots < p_r \le n$ are all of the primes no larger than $n$. Let $P(n) = p_1p_2\cdots p_r+1$ and let $p$ be a prime dividing $P$; then $p$ can not be any of $p_1,p_2,\cdots,p_r$, otherwise $p$ would divide the difference $P(n)-p_1p_2\cdots p_r=1$, which is impossible. So this prime $p$ is still another prime, and $p_1, p_2, \cdots, p_r$ would not be all of the primes.

It is a common mistake to think that this proof says the product $P(n)=p_1p_2\cdots p_r+1$ is prime. The proof actually only uses the fact that there is a prime dividing this product.

Further considerations need you to compute $\frac{P(n)-1}{M}$, modulo $M$. We guarantee that $M$ is a prime number.

Input

The input contains several test cases. The first line of the input is a single integer $t~(1\le t\le 5)$ which is the number of test cases. $t$ test cases follow.
Each test case contains two positive integers $n~(M\le n\le 5\times 10^8)$ and $M~(3\le M\le 2000)$.

The sum of $n(s)$ for all test cases would not be larger than $5\times 10^8$.

Output

For each test case, you should output $\frac{P(n)-1}{M}$ module $M$.

10
13 13
17 13
19 13
23 13
29 13
1300 13
1700 13
1900 13
2300 13
2900 13

Case #1: 9
Case #2: 10
Case #3: 8
Case #4: 2
Case #5: 6
Case #6: 4
Case #7: 8
Case #8: 11
Case #9: 2
Case #10: 9