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, where3≤i≤NP. Here P Hi represents the height of i-th 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, where2≤i≤NH PRi = (H ∗ PRi−1 + I ∗ HHi−1 + J)%100000 + 1, where2≤i≤NH Here HHi represents height of i-th home and PRi represents number of pillars required to build wall for i-th 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.
2/2 Sample Input 1 10 4 2 10 19 121111 Sample Output Case 1: 2