In the 2019 Autumn Event E1 of Kantai Collection, the 8th Destroyer Division is discussing how to bully DJ.

Ooshio says that the Daihatsu landing craft on her left hand can deal $g_0 = a$ damage to DJ, and the tank on her right hand can deal $g_1 = b$ damage to DJ.

Michishio says that for the new anti-land weapons developed by the headquarters, the $i$-th weapon can deal $g_i = 3 \cdot g_{i-1} - g_{i-2}$ damage to DJ.

Arashio says that the headquarters has discovered DJ's weakness, which allows for dealing massive multiplier damage, defined by the following formulas: $$f_{n,0} = n, \quad f_{n,k} = f_{g_n, k-1}$$

Asashio now knows the values of $a, b, n, k$ and has reported them to you, the Admiral. Please calculate the total damage that can be dealt to DJ.

Report the result of the answer modulo $p$ to the 8th Destroyer Division on the front lines.

Input

The first line contains an integer $T$, representing the number of test cases.

Each of the next $T$ lines contains five integers $a, b, n, k, p$, with meanings as described in the problem.

Output

For each test case, output a single integer representing the answer.

Examples

Input 1

1
0 1 2 2 1000

Output 1

8

Note

For all data, $0 \le a, b < p$, $1 \le T \le 1000$, $1 \le n, p \le 10^9$, $1 \le k \le 100$.

For 20% of the data, $k \le 1$.

For 60% of the data, $k \le 2$.