Problem Description

You are given a non-negative integer array $\{a_i\}$ of length $n$. Little L defines a magical transform:

Little L plans to do something interesting with the sequence $f$ generated by this transform, but he is not good at multiplication, so he asks you for help and hopes you can compute $f_{1\dots n}$ as quickly as possible.

Input Format

The input contains multiple test cases.

The first line contains an integer $T$, which indicates the number of test cases.

The next $2T$ lines describe the test cases, with every two lines forming one test case.

In each test case, the first line contains an integer $n$, which is the length of the array $\{a_i\}$. The next line contains $n$ integers describing the array $\{a_i\}$.

It is guaranteed that the input $a_i$ satisfy $0\le a_i\le10^9$. In one test file, it is guaranteed that $\sum n\le 4\times 10^5$.

Output Format

We do not want you to output too many numbers. Therefore, let $ans=\bigoplus_{i=1}^{n}f_i$, where $\bigoplus$ denotes the XOR operation, which can be written as ^ in C++ / Java / Python.

For each test case, output one integer per line, representing $ans$.

2
3
2 3 3
5
1 2 3 4 5

32
4675

Hint

For $100\%$ of the testdata, $0\le a_i\le10^9$, $1\le n\le 2\times 10^5$, and $\sum n\le 4\times 10^5$.

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2017.

Translated by ChatGPT 5