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.
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$.
For each test case, you should output $\frac{P(n)-1}{M}$ module $M$.