Graph Of Zhuper

Time Limit: 24000/12000 MS (Java/Others)

Memory Limit: 256000/256000 K (Java/Others)

Description

We define $Zhu(G)$ as the value of $G$.( $G$ is labeled undirected graphs with $n$ nodes( self-loop and multiple edge are not allowed ) ).

The method of calculating Zhu(G) is easy , if $G$ has $K$ connected components, then Zhu(G) = $gcd(size_1,size_2,...,size_k)$

* $size_k$ is the number of vertexs in connected component $k$

Now, Shen wants to know $\sum_{}{}Zhu(G)$, can you help him?

Because the answer may be large, so you are only need to output the answer modulo $P$.

Input

The first line is an integer T($1 \leq T \leq 10$) describe the number of test cases.

For each testcase, the first line contains two numbers $n$ and $P$.

You can assume that $1 \leq n \leq 30000 , 100000000 \leq P \leq 1000000009$

There are no more than $5$ testcases with $n \geq 10000$.

It is guaranteed that $P$ is a prime number.

Output

For the $k$th test case , first output "Case #k: " , then output an integer as answer in a single line.

Sample Input

3 1 1000000007 2 1000000007 3 1000000007

Sample Output

Case #1: 1 Case #2: 3 Case #3: 16

Hint

liuyiding

Source

2017中国大学生程序设计竞赛 - 网络选拔赛

提交代码