Gorwin is very interested in equations. Nowadays she gets an equation like this
$\begin{array}{l}
0 \le {x_i} \le n{\kern 1pt} {\kern 1pt} {\kern 1pt} for{\kern 1pt} {\kern 1pt} {\kern 1pt} 1 \le i \le n\\
{x_i} \le {x_{i + 1}}{\kern 1pt} \le {x_i} + 1{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} for{\kern 1pt} {\kern 1pt} {\kern 1pt} 1 \le i \le n - 1
\end{array}$
For a certain $n$, Gorwin wants to know how many combinations of $xi$ satisfies above condition.
For the answer may be very large, you are expected output the result after it modular $m$.
Input
Multi test cases. The first line of the file is an integer $T$ indicates the number of test cases.
In the next $T$ lines, every line contain two integer $n, m$.
[Technical Specification]
$1 \leq T < 20$
$1 \leq n \leq 50000$
$1 \leq m \leq 1000000000$
Output
For each case output should occupies one line, the output format is Case #id: ans, here id is the data number starting from 1, ans is the result you are expected to output.
See the samples for more details.
