You and Dope are visiting DAKSH. Suddenly Dope found some balls having some mass on it and all balls are white in color. They found an interesting thing of the balls that they can change color to either red or green on clicking the switch on it. Dope is in a funny mood and wants to play a game with you. He tells you that each player will switch the balls to either red or green color alternatively and only white ball can be chosen to change the color. After changing the color of all balls you need to pay an amount equal to the absolute difference between mass of the red balls and green balls. Dope would try to maximize the pay and obviously you want to give him as little as possible. Dope invites you to play first. If you and Dope play optimally, what is the amount you have to pay to Dope?

Input

T number of test cases. Each case consists of two lines. first line N number of white balls. Next line contains a b c use to generate N mass using:

mass = (a * i + b) % c; for 1 <= i <= N

Output

A single line for each case containing the amount you need to pay.

Constraints

1 <= T < 1000

1 <= N < 10000

1 <= a, c < 1000

0 <= b < 1000

Example

Input:
2
3
1 0 10
4
2 1 10

Output:
2
10

Explanation

Case 1: 3 mass = 1 2 3; output = 2

Case 2: 4 mass = 3 5 7 9; output = 10