hyperoperations

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 1000000000

Sample Output:

3
4
3
7
312
884765625