Relocation Game

Tourist ( Gennady Korotkevich ) is a famous competitive programmer. He has won two ACM ICPC World Finals. Thanks to his sublime performance in contests, he has become very popular all over the world!

One day Tourist came across an interesting problem. It goes like this:

You are given an array A of N integers named A0 , A1 , ... , AN-1. The array elements are in the range [0,N-1]. You have to rearrange the elements in a non-decreasing order. Let Pi denote the location of the value Ai after the rearrangement is done. The cost of this rearrangement is the sum of | Pi - i | for all 0 ≤ i ≤ N-1. Here, |x| denotes the absolute value of x. You have to find the minimum cost of such a rearrangement.

These days Tourist is too busy playing the new arcade game, Forthright on his dearest gaming PC. So he asks you, his favorite underling, to solve this problem.

Input

The first line of input contains an integer T, the number of test cases for the problem. Each of the following T lines describe a test case.

For each test case, you are given four integers in the following order: N (the number of elements in array A), A0 (the first element of array A), B and C. Ai for 1 ≤ i ≤ N-1 is calculated using the formula Ai = ( ( Ai-1 * B ) + C ) % N.

Constraints:

1 ≤ T ≤ 104
1 ≤ N ≤ 104
0 ≤ Ai < N for all 0 ≤ i < N
0 ≤ B, C ≤ 109

Notice that both the initial array and the array after rearrangement have 0-based indexing.

Output

For each test case, output the minimum cost of rearrangement for that case in a separate line.
Please take a look at the sample input/output to get a better understanding of the format.

Sample

Input	Output
2 4 3 5 3 4 0 1 1	8 0

Explanation

Case 01:
Before rearrangement, A = [ 3, 2, 1, 0 ]
After rearrangement, A = [ 0, 1, 2, 3]
P = [ 3, 2, 1, 0 ]. Hence, cost = | 3 – 0 | + | 2 – 1 | + | 1 – 2 | + | 0 – 3 | = 8.

Case 02:
Before rearrangement, A = [ 0, 1, 2, 3 ]
After rearrangement, A = [ 0, 1, 2, 3]
P = [ 0, 1, 2, 3 ]. Hence, cost = | 0 – 0 | + | 1 – 1 | + | 2 – 2 | + | 3 – 3 | = 0.