There is a biology experiment going in the biotech. lab of the "very prestigious" DTU. The students there are trying to study the reproduction patterns of a newly discovered species of virus pabbu-pneumoniae ;)

These pabbu-pneumoniae virus reproduce in a rather strange and fascinating way.

After adding "a" number of viruses to the petri dish on the first day of the experiment they make the following observations:

On the second day, they found that the virus' number had been increased by "d".

On the third day, they found that the new number of viruses in the dish was "r" times the number recorded on the second day.

On the fourth day, they again found that the number had increased by "d" by that recorded on the third day... and so on...

The pabbu-pneumoniae virus never cease to reproduce.

For example, if d=1, r=4 and a=1..then the number of microbes recorded on each day would be: 1 2 8 9 36 37 148 149...

Given 'a', 'd', 'r' and 'n', you have to find the number of microbes in the petri dish at the end of the n'th day.

Since the numbers can be pretty large, you are required to print the answer modulo a number "m" ("m" will be supplied for each case)

Input

First line of input will have number 'T', the number of test cases. [T <= 2000]

Each of the test cases will have 2 lines -:

First line will have 3 space-separated numbers 'a','d'  and   'r' respectively.

2nd line will have 2 space-separated numbers 'n' and 'm' respectively.

Output

For each test case print the required answer in a separate line.

NOTE - The value of a, d, r, n and m will be more than 0 and less than 10^8.

Example

Input:
1
1 2 3
4 5

Output:
1

Explanation: The sequence is - 1, 3, 9, 11, 33, 35, 105... The 4th term is 11 and 11 % 5 = 1