B. XORnacci
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given the first $$$m$$$ elements of an infinite sequence $$$a_1, a_2, \ldots, a_m$$$.

For every index $$$i \gt m$$$, the sequence is extended according to the following rule: $$$$$$ a_i = a_{i-2} \oplus a_{i-1}, $$$$$$ where $$$\oplus$$$ denotes the bitwise XOR operation.

Your task is to determine the value of $$$a_1 \oplus a_2 \oplus \cdots \oplus a_n$$$, that is, the bitwise XOR of the first $$$n$$$ elements of the sequence.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$2 \le m \le n$$$, $$$m \le 2 \times 10^5$$$, $$$n \le 10^9$$$).

The second line of each test case contains $$$m$$$ space-separated integers $$$a_1, a_2, \ldots, a_m$$$ ($$$0 \le a_i \lt 2^{30}$$$) — the first $$$m$$$ elements of the sequence.

It is guaranteed that the sum $$$m$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output a single integer in a line – the bitwise XOR of the first $$$n$$$ elements of the sequence.

Example
Input
3
5 4
1 2 3 4
8 3
3 5 14
100 2
0 0
Output
3
6
0
Note

In the first test case, $$$a_5 = a_4 \oplus a_3 = 4 \oplus 3 = 7$$$. So, the bitwise XOR of the first $$$5$$$ elements of the sequence is $$$1 \oplus 2 \oplus 3 \oplus 4 \oplus 7 = 3$$$.

In the third test case, all the elements in the sequence are $$$0$$$, and so the bitwise XOR of the first $$$100$$$ elements is also $$$0$$$.