# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Jontrona!

By msabeer · Limits 3s, 512 MB

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.

## Sample

InputOutput
2
1 10 2
3 7 3

Case #1: 6
Case #2: 6


### Statistics

24% Solution Ratio

abcdef123Earliest, Jul '20

AnachorFastest, 0.6s

steinumLightest, 131 kB

Sumaya_1703110Shortest, 755B