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

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

hide comments
2012-10-01 00:33:28 Robert Gerbicz
The speed comparison is hard, on the Cube I have got 0.00 sec., here 0.03 sec.
2012-09-28 21:36:58 Jared Deckard
Sample output should be
2
1
292
2012-09-28 10:56:50 Chef
yes how can the output be 6 if the modulus d=5 ?
2012-09-28 10:22:28 Damian Straszak
how can the output be 6 if the modulus d=5?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.