Easy
Math > Counting

Professor Mahammad likes playing with arrays, today he invented another interesting game for you. Here it is.
Professor defines **goodness values** of array **a** over a fixed value **M** as the number of subarrays (contiguous subsequence) of this array having the sum divisible by **M**. Let's define this goodness value as **g(a, M)**.
For example, if **a = [2, 3, 4, 2] and M = 3**, we get **g(a, M) = 4** because the following **4** subarrays have a sum which is multiple of **M**: **{[2, 3, 4]; [3], [3, 4, 2], [4, 2]}**.
Now, consider all possible **cyclic shifts** of the array **a**, surely we have **N** of them. Your task is quite simple, just find the number of cyclic shifts of **a** which have maximum goodness value over the given **M**.
Input:
------
The very first line of the input contains an integer **T (1 ≤ T ≤ 10)**, denoting the number of test cases.
Each test case consists of 2 lines. The first one contains an integer **N (1 ≤ N ≤ 10^3)** and **M (1 ≤ M ≤ 10^5)** denoting the number of elements of the array and the fixed number **M**, respectively. The next line will contain **4** integers separated by spaces, denoting **a[1]**, **A**, **B** and **C (1 ≤ a[1], A, B, C ≤ 10^5)** .
Simply, you are given **a[1]** and other remaining elements can be calculated as **a[i] = (a[i - 1] * A + B) % C** where **2 ≤ i ≤ n**.
Output:
-------
For each test case, print an integer, describing the number of cyclic shifts having maximum goodness value.
Sample Input
------------
1
3 2
5 4 10 9
Sample Output
-------------
2
Note: After generation, our array will be **a = [5, 3, 4]** and **M = 2** is given.
1st cyclic shift of **a** --> [5, 3, 4], g(a, M) = **3**; **{[5, 3], [5, 3, 4], [4]}** are good subarrays.
2nd cyclic shift of **a** --> [3, 4, 5] g(a, M) = **2**; **{[4], [3, 4, 5]}** are good subarrays.
3rd cyclic shift of **a** --> [4, 5, 3] g(a, M) = **3**; **[4], [4, 5, 3], [5, 3]}** are good subarrays.
Since 1st and 3rd cyclic shifts have the maximum goodness value 3, answer is 2.

#### Please login to submit solution to this problem.