If the starlight never fade

Problem Description

We will give you a non-negative integer $m$ and a prime number $p$.
And we define $f\left(i\right)$ is the number of pair$\left(x,y\right)$ that satisfies $\left(x + y\right) ^ {i} \equiv x ^ {i} \% p$ and $1 \leq x \leq p - 1,1 \leq y \leq m$. Now, you have to calculate the sum $\sum_{i=1}^{p-1}if\left(i\right)$.
Maybe the sum is too big,so you only need to output the sum after mod $1e9+7$.

Input

The first line contains only one integer $T$, which indicates the number of test cases.
For each test case, there are a integer $m \left(1 \leq m \leq p - 1 \right)$ and a prime number $p\left(2 \leq p \leq 1e9 + 7 \right)$ on one line.

Output

For each test case, output one line "Case #x: y", where x is the case number (starting from 1) and y is the sum after mod $1e9+7$.

Sample Input

3

5 7

3 11

2 103

Sample Output

Case #1: 210

Case #2: 390

Case #3: 50388

Source

2017 Multi-University Training Contest - Team 2

https://acm.hdu.edu.cn/showproblem.php?pid=6051