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

Submit

Login to submit.

Contributors

Statistics

29% Solution Ratio
abcdef123Earliest, Jul '20
seyamalamFastest, 0.3s
steinumLightest, 131 kB
seyamalamShortest, 691B
Toph uses cookies. By continuing you agree to our Cookie Policy.