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 - Cube 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