FIBONACCI is the recursive sequence that is given by: F(n)=F(n-1)+F(n-2) with F(0)=0 and F(1)=1
In this problem we define FIBOSQRT that is given by: Fs(n)=Fs(n-1)+Fs(n-2)+2*SQRT(3+Fs(n-1)*Fs(n-2)) with Fs(0) and Fs(1) are given in the input file.
It's guaranteed that SQRT(3+Fs(n-1)*Fs(n-2)) is always an integer.  I've proved it by math theorem.

Now your task is to find Fs(n)
Since the number can be Big you have to find the result mod M.

Input

The first line is an integer T(1 ≤ T ≤ 111,111), denoting the number of test cases. Then, T test cases follow.

For each test case, there are four integers Fs(0),Fs(1)(1 ≤ Fs(0) ≤ Fs(1) < 10⁶), M(1 ≤ M < 10⁹), and n(0 ≤ n < 10¹⁸) written in one line, separated by space.

Output

For each test case, output Fs(n) mod M.

Example

Input:

2

1 1 10 5

2 3 100 6
Output:

</p>

4

82

Explanation:

Case #1:

• Fs(0)=1
• Fs(1)=1
• Fs(2)=1+1+2*SQRT(3+1*1)=6
• Fs(3)=6+1+2*SQRT(3+6*1)=13
• Fs(4)=13+6+2*SQRT(3+13*6)=37
• Fs(5)=37+13+2*SQRT(3+37*13)=94

The answer is: 94 mod 10 = 4.

Case #2:

• Fs(0)=2
• Fs(1)=3
• Fs(2)=3+2+2*SQRT(3+3*2)=11
• Fs(3)=11+3+2*SQRT(3+11*3)=26
• Fs(4)=26+11+2*SQRT(3+26*11)=71
• Fs(5)=71+26+2*SQRT(3+71*26)=183
• Fs(6)=183+71+2*SQRT(3+183*71)=482

  The answer is: 482 mod 100 = 82.

Input File:

File #1: More than 100,000 random test cases (test your program speed )

File #2: Less than 10 test cases (tricky test cases that might give you WA )

 

Time Limit ≈ 8*(My Program Top Speed)

 

Warning: large Input/Output data, be careful with certain languages

See also: Another problem added by Tjandra Satria Gunawan