## SPEEDCUB - Speed test - Cube version

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 23Output:6 5 284

Added by: | wiele |

Date: | 2012-09-22 |

Time limit: | 5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |