It's a bright, cheerful day in the whimsical town of Permexorpia. This peculiar place has a tradition that has never been seen before: friends exchange elaborate mathematical objects as tokens of affection. Today, we witness our dear friend Alice meticulously preparing a special present for her companion, Bob. Knowing Bob’s fondness for rare types of sequences, Alice has crafted an incredibly thoughtful and unique gift—a beautifully wrapped permutation.

In Permexorpia, a permutation of size $$$n$$$ is a list containing each of the numbers $$$0, 1, 2, ..., n-1$$$ exactly once (notice the list contains $$$0$$$ and does not contain $$$n$$$).

Upon receiving this extravagant gift, Bob, who is an avid enthusiast of unusual mathematical operations, decides to compute something truly intriguing: the XOR of the MEX of every single possible continuous subarray† of the permutation given by Alice. More formally, let $$$f(p)$$$ be the value calculated by Bob for a given permutation $$$p$$$. We have:

Where $$$p[i,j]$$$ denotes the subarray $$$[p_i, p_{i+1}, p_{i+2} ..., p_{j-1}, p_j]$$$, mex denotes the Minimum Excluded value and $$$\oplus$$$ denotes the XOR operation.

† A continuous subarray of an array $$$a$$$ is an array obtained by deletion of several (possibly zero) elements from the beginning of $$$a$$$ and several (possibly zero) elements from the end of $$$a$$$, while keeping the remaining elements in the same order.

Input

The first line contains an integer $$$t$$$ – the number of independent test cases ($$$1 \leq t \leq 10^4$$$).

Each test case consists of two lines. The first line of each test case contains an integer $$$ n $$$, the size of the permutation $$$p$$$.

The following line contains $$$n$$$ distinct integers $$$p_1, p_2, \dots, p_n$$$, each integer raging from $$$0$$$ to $$$n - 1$$$.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$5 \cdot 10^5$$$ over all test cases.

Output

Output a single integer — the value of $$$f(p)$$$, the XOR of the MEX values of all possible continuous subarrays of the given permutation.

Example

Input

3
3
1 0 2
4
0 1 3 2
1
0

Output

1
5
1

Note

Recall that the MEX (Minimum EXcluded value) of a sequence is the smallest non-negative integer that does not appear in the sequence. For instance:

• The MEX of [0, 1, 2] is 3.

• The MEX of [1, 2] is 0.

• The MEX of [0, 2, 3] is 1.