SPEEDPYR - Speed test - Pyramid 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 - 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

hide comments
Robert Gerbicz: 2012-10-01 00:33:28

The speed comparison is hard, on the Cube I have got 0.00 sec., here 0.03 sec.

Jared Deckard: 2012-09-28 21:36:58

Sample output should be
2
1
292

Chef: 2012-09-28 10:56:50

yes how can the output be 6 if the modulus d=5 ?

Damian Straszak: 2012-09-28 10:22:28

how can the output be 6 if the modulus d=5?


Added by:wiele
Date:2012-09-22
Time limit:3.365s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64