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

3
1 1000000007
2 1000000007
3 1000000007

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