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,MN, M and KK 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 TT, the number of test cases. Then the following TT lines will contain three integers N,MN, M and KK.

Constraints:

1T101 \le T \le 10
1N1091 \le N \le 10^9
1M21071 \le M \le 2*10^7
0K1090 \le K \le 10^9

Output

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

Sample

InputOutput
2
1 10 2
3 7 3
Case #1: 6
Case #2: 6

Discussion

Statistics


24% Solution Ratio

abcdef123Earliest, Jul '20

AnachorFastest, 0.6s

steinumLightest, 131 kB

Sumaya_1703110Shortest, 755B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.