Equation

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$.

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$

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.