Let F0 = 1. Fn = a*Fn-1 + b for n >= 1. Find Fn (mod M).

Input

The first line contains T the number of test cases. Each of the next T lines contains 4 space seperated integers a, b, n and M.

Constraints

T <= 20000
0 <= a, b, n <=  10^100
1 <= M <= 100000

Output

Output T lines, one corresponding to each test case.

Example

Input:
3
1 1 1 10
2 1 2 5
5 2 20 30

Output:
2
2
7