## FIBOFUN - Fun with Fibonacci Series

no tags

Fibonacci series is a series in which every element is sum of previous 2 elements.

first 2elements are 0,1 and the series goes like 0,1,1,2,3,5,8,13 ........

What if you were given 2 random numbers as the starting of the series and u follow the same rule as the fibonacci rule.

for eg. if you were given 2 and 2 .. the series would become

2 2 4 6 10 16 26 .........

Now ur task is Simple ...

You will be given 2 numbers a & b .. the first and second term of the series..

you need to calculate the sum of first n numbers of the series so formed..

Since the numbers can be big you need to print the result mod some number 'M' provided in the input.

### Input

first line will have single number 't' - number of test cases.

each test case will have 4 numbers a,b,n & M

a- first number of the series

b- second number of the series

n- calculate the sum till n numbers

M- print the result mod M

### Output

single number for each case - sum of n terms mod M

### Example

```Input:
22 2 10 211 3 10 21 Output:
134Explanation - for first case series is 2 2 4 6 10 16 26 42 68 110 .. Sum is 286.. o/p = 286%21 = 13NOTE -Number of test cases <=100.0 <= a,b,m <= 10^8
1 <= n <= 10^8
actually n ranges from 1 to 10^8

```