问题描述
Gorwin 对等式非常感兴趣。前几天他获得了这么一个等式
${x_1} + {x_2} + {x_3} + \cdots + {x_n} = n$, 这里 \[\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}\]
对于一个给定的$n$,Gorwin想要知道有多少$xi$的组合满足上述等式。
由于结果比较大，输出答案对$m$取余的结果就行。
输入描述
多组测试数据。文件的第一行给出一个$T$，表示下面有$T$组数据。下面$T$行每行给出两个整数$n,m$以一个空格分开。
[参数约定]
$1 \leq T < 20,1 \leq n \leq 50000,1 \leq m \leq 1000000000$
输出描述
对于每一个数据输出占一行，输出格式为Case #id: ans，这儿id是数据编号从1开始，ans是你输出的答案。
看样例得到更多信息。
输入样例
2
3 100
5 100
输出样例
Case #1: 2
Case #2: 3
