## SPEEDCUB - Speed test - Cube version

no tags

This problem was created to compare speed of the Pyramid and Cube Clusters. After you get AC result for this problem you can submit solution to problem called Speed test - Pyramid version - both problems have identical statement and test cases.

### Input

There is a single positive integer t (2 <= t <= 10000) on the first line of input which corresponds to the number of tests. Then t lines follow, each containing five numbers: a, b, c, d, h (2 <= a, b, c, d, h <= 10000). For each line you should do the following thing:

•     Step 0
• a) Assign a to r1.
•     Step 1
• b) Take r1, add b to it and you get r2.
• c) Take r2, multiply it by c and you get r3.
• d) Now compute r1 = r3 modulo d.
•     Steps 2, 3, ... , h
• e) Do b), c) and d) (h-1) times.

### Output

t lines containing one number: r1

### Example

```Input:
3
2 3 4 5 2
5 8 9 4 9
23 15 923 489 23

Output:
6
5
284
``` Francky: 2015-01-24 22:52:43 Now both problems are strictly identical ;-)