This is the year 9002, the war between the Earth and Triton has broken out. Being a spy for the Earth, you are trying to find all means to destroy Triton protections. Being a very smart spy, you have somehow managed to enter into the Triton network and take over the control of a gateway. Now, you are trying to decode the messages passed between them. The messages are arbitrarily long sequence of integers with a preamble of P integers. Each integer will fit inside a 32 bit signed integer. You have managed to capture the actual preamble. But, the communication lines are too noisy, and for this reason, you can not get the sequence accurately. For each number in the sequence si, you have determined that, it can actually be any value between pi and qi inclusive. Now, given the sequence of numbers, find in how many places, the message may start. Input First line contains T, the number of test cases. Each test case starts with an integer P, the length of the pattern. The next line contains P integers. Next line contains 10 integers, N, p0, q0, A, B, C, D, E, F, M. N is the length of the sequence. The range for each element in the sequence is generated using a generator function pi =(A∗pi−1 +B∗qi−1 +C)%M qi =(D∗pi−1 +E∗qi−1 +F)%M if(qi < pi) swap(pi, qi) [p1, q1], [p2, q2], ..., [pN , qN ] describes the sequence. sequence. Output Please note that [p0, q0] is not included in the For each test case, output the number of places, the preamble may start. Constraints • T ≤ 100 • P ≤ 60 • N ≤ 1000000 • 0 ≤ p0,q0,A,B,C,D,E,F,M ≤ 1000000000 Notes: In the first case. the intervals are: [8,14],[10,16],[12,18],[14,20]. The value 10 can only be contained in the first two. In the second case, all the intervals are [1,3], so, you can find two positions to start the preamble.
2/2 Sample Input 2 1 10 4 6 12 1 0 2 0 1 2 100000 2 12 3 1 3 1 0 0 0 1 0 10 Sample Output Case 1: 2 Case 2: 2