Isfan vai is on high demand nowadays. You know why, right? However, his best friend is somewhat disappointed with Isfan's single life and decided to dedicate a problem statement for him. Then he thought, nah let's not disclose it and let him remain single forever! So, his friend, setter of the problem, decided to keep the problem straight-forward. Here goes the problem:-

Given the following segment of code and parameters $N, M$ and $K$ for solve() function:-

int f(long long a, int m){
return (a * a + a) % m;
}
int solve(int N, int M, long long K){
int a = N % M;
for(int i = 0; i < K; i++){
a = f(a, M);
}
return a;
}

What will the solve() function return?

It's not my fault if the code runs too slow. Do you have any working solution under the given time limit?

Input

The first line will contain a single integer $T$, the number of test cases. Then the following $T$ lines will contain three integers $N, M$ and $K$.

Constraints:

$1 \le T \le 10$ $1 \le N \le 10^9$ $1 \le M \le 2*10^7$ $0 \le K \le 10^9$

Output

For each test case output "Case #X: Y"(without quotes) where $X$ means the number of test case starting from $1$ and $Y$ is the return value of solve function.