|
D |
Home!
Sweet Home! Input: Standard Input Output: Standard Output |
|
Own home is the sweetest place if it is really secured. People build wall around home to make their home more secured. Some pillars are required to make more strong wall. There is a shop named “Home! Sweet Home!”, which sells pillar specially made for building walls. This is really a busy shop. Everyday lot of contractors come, who are responsible for building walls, having a list of homes in their hands. Their list usually contains information of homes specially height of the home and number of pillars required to build that home. |
|
They find pillars are arranged in a row in that shop. Every pillars in row are tagged with heights. Every contractors want to buy some pillars such that they can make walls for all those homes in their list. But unfortunately the shop has some limitation of pillars. So the owner of that shop decides to hire you to write a program for them, which can calculate the number of maximum possible home, for which the contractor can build wall using the pillars in that shop.
Note that, a pillar having less height than a home cannot be used to build wall in that home for security purpose.
Input
First line of input will contain a number T(1<=T<=200), which indicates the number of test cases. Each test case starts with a line having two integers NP and NH(1<=NP<=100000, 1<=NH<=100000), number of pillars in “Home! Sweet Home!” and number of homes in contractor's list. The next line will contain three integers A, B and C (1 <= A, B, C <= 10000). You can calculate height of the pillars of the shop by this way -
PH1 =
C % 10000 + 1
PH2 =
(A * PH1 + C) % 10000 + 1
PHi =
(A * PHi-1 + B * PHi-2 + C) % 10000 + 1, where
3<=i<=NP.
Here PHi represents the height of ith pillar in the row of the shop.
The next line will contain six integers E, F, G, H, I and J. (1 <= E, F, G, H, I, J <= 10000). You can generate the height of the homes and number of pillars required for corresponding homes in the list by this way –
HH1 =
G % 10000 + 1
PR1 =
J % 100000 + 1
HHi =
(E * HHi-1 + F * PRi-1 + G) % 10000 + 1, where
2<=i<=NH
PRi =
(H * PRi-1 + I * HHi-1 + J) % 100000 + 1, where
2<=i<=NH
Here HHi represents height of ith home and PRi represents number of pillars required to build wall for ith home.
Output
For each test case, output a single line of the form “Case X: N”, where X denotes the case number and N denotes the maximum number home for which it is possible to make a wall.
Sample
Input Output
for Sample Input
|
1 10 4 2 10 19 1 2 1 1 1 1 |
Case 1: 2 |
Problem setter: