In this problem, we generalize the Fibonacci sequence.

    G[n] = a * G[n - 1] + b * G[n - 2] + c

where a, b and c are constants given in input. Also:

• G[1] = 1
• G[2] = 1

You need to evaluate the nth number module m in the generalized Fibonacci sequence where m is given in input.

Input

The first line contains number of test cases t. Each of the next t subsequent lines contain a, b, c, n and m.

t <= 1000

0 <= a, b, c <= 1e9

1 <= m <= 1e9

1 <= n <= 1e18

Output

Print answer for each test case on a separate line.

Example

Input:
1
1 1 0 3 5

Output:
2