Ever done exponentiate? Yes? Good!

Now you need to calculate the hyperoperations!

You are given 4 numbers, T,A,B,M.
You are supposed to do the T'th operation on A, B times and output the remainder of the result divided by M.

- 1: successor
- 2: addition
- 3: multiplication
- 4: exponentiation

Of course, 4 is tetration. Have fun!

7^^4 = (7^(7^(7^7)));

X^^0 = 1 for all X

Constraints:

0 <= T,A,B,M <= 2^32-1

0 <= N <= 100000

Subtasks:

Subtask 1: T <= 1 (1%)

Subtask 2: T <= 2 (2%)

Subtask 3: T <= 3 (3%)

Subtask 4: T <= 4 (14%) If T is 4, 1<=A,B,M<=100

Subtask 5: T <= 4 (80%)

Input: First line: N, number of testcases

Subsequent N lines, 4 integers, T,A,B,M

Output: For each testcase, output the result

Sample Input:

6 1 1 2 10 2 2 2 10 3 3 3 4 4 3 2 20 4 3 3 345 4 993306745 75707320 1000000000Sample Output:

3 4 3 7 312 884765625

Subtask | Score |
---|---|

1 | 1 |

2 | 2 |

3 | 3 |

4 | 14 |

5 | 80 |