PLAYSIGN - color the balls

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


Added by:pankaj
Date:2011-02-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own, DOPE 2011

hide comments
2023-10-02 16:09:18
baler problem
2013-07-20 14:39:00 Nilanjana Das
I am trying greedy approach but am getting wrong answer. Could someone suggest some tricky test cases plzz..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.