Alice plays web browser games a lot. She turns her focus on a new two player PVP game recently. The game consists of N rounds and N + 2 cards. Each card has an non-negative integer on its face while all of them having the same picture on their back sides. After two players connect to the battle field, the cards will be shued and put face down as the card pool. Then the top two cards from the pool will be placed on two initially empty card stacks face up one on each stack. Then two positive numbers w1, w2 will be randomly decided and maintain xed during the game as the weights of the stacks to nish the initial setting. Note that two players are not sharing the battle
eld but play on the identical mirror version of their own. For the rest of the game two player will play N rounds independently. In each round two players will draw the top card from the pool(two players will get the same card for the same round), look at its number and make a choice to place the card face up on top of one of the two stacks. The score gained by placing a card with number x on a stack with a top card numbered y is ws jx - yj where ws is the stack's weight.
Alice thought the game was purely based on luck at rst. But she soon nds out that she can never get a better score than Kirito in the game no
matter how hard she tried. Alice is sad and keep asking Kirito what's the trick behind. At last Kirito told her the secret to win. Kirito said that he
hacked into the system and he can get the following parameters before the game start: w1, w2, c1, c2, d1, d2, a, b, c, m. The c1 and c2 indicating the
number of initial cards on the stacks. The card drawn in the ith round would be di and di = (di-1 × a + di-2 × b + c) mod m for i > 2.
While Kirito can determine the best strategy with there parameters, Alice decided to learn the hacking technique from Kirito and leave the strategy part to you. So your job is to write a program to tell the highest score possible given the parameters.
The first line of the input data contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.
The first and only line of each test case contains eleven integers N, w1, w2, c1, c2, d1, d2, a, b, c, m (1 ≤ N ≤ 107, 0 ≤ w1,w2 ≤ 1000, 0 ≤ a, b, c, c1, c2, d1, d2 < m ≤ 108) indicating the number of rounds and the parameters of card generation(see the problem description part). Note that for at least 95% of the test cases N ≤ 104.
Please consider the card generation formula as a random number generator and has absolutely no relation to the intended solution. The intended solution works for any valid card number sequences without the mathematical restriction due to the formation of the generation formula stated.
For each test case, output a single line containing the number of possible highest score.