Easy Peasy, Lemon Squeezy

Let's consider an array $A$ which is initially empty. We'll perform two types of operation on that array:

1. Add an element $X$ at the end of the array.
2. Remove the last element of the array.

Let's define beauty value of the array $A$ as the summation of the maximum and the minimum elements of the array. For example, let's assume at any instance the array $A$ is $[3, 2, 4]$. The maximum element is: $4$, and the minimum element is: $2$. So the beauty value of the array at that instance is $2 + 4 = 6$.

At any point, if the array $A$ becomes empty, the value of the maximum and minimum is 0 i.e. the beauty value is 0 then. At any point, if you are asked to perform the second operation (removing the last element of the array) while the array $A$ is empty, you have to ignore that operation.

There will be multiple testcases in this problem. In each case, you have to process $N$ operations. In each operation, you'll be given the type of the operation. If the type of the operation is of first kind, then you'll be given another integer $X$, you have to add $X$ at the end of the array. If the type of the operation is of second kind, you have to remove the last element of the array. After each operation, you have to find the beauty value of the array $A$. So, you will have $N$ beauty values. You have to find the $XOR$ (Exclusive OR) of all the beauty values.

$XOR$ is a bitwise logical operation that outputs true only when inputs differ (one is true, the other is false). The truth table for all combinations of bits has given below:

0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0

Input

Input starts with an integer $T$ ($1 \leq T \leq 10$), the number of testcases.

The first line of each testcase will contain an integer $N$ ($1 \leq N \leq 10^7$), the number of operations. Instead of description of $N$ operations, the next line will contain 4 integers, $a$, $b$, $c$ and $m$ ($1 \leq a, b, c, m \leq 10^8$). You have to use following formula to generate some integers $V_i$, which is necessary to find the type of $i$-th operation and the value to insert if the operation is of type 1.

$V_i = a \times V_{i-1} + c \pmod m$, where, $V_0 = b$.

If $V_i$ is odd, then you have to add $V_i$ at the end of the array, i.e. $X = V_i$. If $V_i$ is even, then the operation is of type 2, you have to erase the last element of the array.

Output

For each testcase, print the $XOR$ of the beauty values of the array after performing each operation.

Sample

Input	Output
1 9 1 2 3 7	12
Initially, $V_0 = 2$. By using equation $V_i = a \times V_{i - 1} + c (mod m)$, $V_1 = 5$, It's odd, 5 is added at the back of the array, hence the array, $A = [5]$, the beauty value of the array is $5 + 5 = 10$. $V_2 = 1$, it's odd too, 1 is added at the back of the array, hence the array, $A = [5, 1]$, the beauty value of the array is $1 + 5 = 6$. $V_3 = 4$, it's even, the last element of the array has removed, hence the array, $A = [5]$, the beauty value of the array is $5 + 5 = 10$. $V_4 = 0$, it's even too, the last element of the array has removed, hence the array, $A = []$, i.e empty, the beauty value of the array is $0 + 0 = 0$. $V_5 = 3$, it's odd, 3 is added at the back of the array, hence the array, $A = [3]$, the beauty value of the array is $3 + 3 = 6$. $V_6 = 6$, it's even, the last element of the array has removed, hence the array, $A = []$, i.e empty, the beauty value of the array is $0 + 0 = 0$. $V_7 = 2$, it's even too, the array is empty, hence skipped the operation, the beauty value of the array is $0 + 0 = 0$. $V_8 = 5$, it's odd, 5 is added at the back of the array, hence the array, $A = [5]$, the beauty value of the array is $5 + 5 = 10$. $V_9 = 1$, it's odd too, 1 is added at the back of the array, hence the array, $A = [5, 1]$, the beauty value of the array is $1 + 5 = 6$. $XOR$ of all the beauty values of the array after performing each operation is $10 ⊕ 6 ⊕ 10 ⊕ 0 ⊕ 6 ⊕ 0 ⊕ 0 ⊕ 10 ⊕ 6 = 12$. Hence, the answer of testcase 1 is 12.