M. Hayyan and Subarray Sums
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of length $$$n$$$. A partition of the array $$$a$$$ is dividing it into subarrays$$$^{[1]}$$$ such that each element of $$$a$$$ belongs to exactly one subarray. Two partitions are considered different if there is a subarray that is present in one of the partitions but not in both of them.

We define the cost of a partition of $$$a$$$ as the following:

  1. Let's initialize cost to be equal to $$$0$$$.
  2. For each subarray of $$$a$$$ (i.e. $$$a[l, l + 1, \ldots, r]$$$) that is present in the partition, let $$$s$$$ be equal to the sum of integers in this subarray (i.e. $$$\displaystyle\sum_{i=l}^r a_i$$$).
  3. Update cost to be equal to cost $$$\oplus$$$ $$$s$$$, where $$$\oplus$$$ is the bitwise XOR$$$^{[8]}$$$ operator.

Find the bitwise XOR of the costs of all possible partitions of $$$a$$$.

Input

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

For each test case, the first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the array $$$a$$$.

The second line consists of $$$n$$$ spaces-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

Output $$$t$$$ lines, the $$$i$$$-th of which contains a single integer — the answer for the $$$i$$$-th test case.

Example
Input
3
1
1
2
1 2
3
1 2 3
Output
1
0
2