It's a bright, cheerful day in the whimsical town of Permuxormexopia. 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 Permuxormexopia, 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 contains $$$n$$$).
Upon receiving this extravagant gift, Bob, who is an avid enthusiast of unusual mathematical operations, decides to calculate the XOR of the MEX of all subarrays† of the given permutation. More formally, let $$$f(p)$$$ be the value calculated by Bob for a given permutation $$$p$$$, we have:
† A subarray of an array $$$a$$$ is an array obtained by deletion of several (possibly none) elements from the beginning of $$$a$$$ and several (possibly none) 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 $$$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) of a sequence is the smallest non-negative integer that does not appear in the sequence. For instance:
The MEX of
[0, 1, 2]is3.The MEX of
[1, 2]is0.The MEX of
[0, 2, 3]is1.
