For a permutation P of N numbers, let us define the cyclic shift of P as another permutation \(P^{d}\) such that \(P^d_i\) = \(P_{i + 1}\) for all i from 1 to \(N - 1\), and \(P^d_N\) = \(P_1\).

We can create N distinct permutations by applying the cyclic shift operation N times.

For an array P of N numbers, let us define the number of inversions in it as the number of pairs \((i, j)\) such that \(i \lt j\) and \(P_i \gt P_j\).

For each of the N distinct permutations created by applying the cyclic shift operations on the initial permutation, consider it as an array of N numbers and find the number of inversions in it. Print the bitwise XOR of the number of inversions in each newly created permutation.

You need to handle T test cases each containing a new permutation.

Input:

First line of input contains an integer T, denoting the number of test cases. Each test case contains 2 lines. First line of each test case contains a single integer N, denoting the number of elements in the permutation P. Next line of each test case contains N space separated integers denoting the permutation P.

Output:

For each testcase, print an integer, the bitwise XOR of the number of inversions in each permutation which are created by cyclic shifts on the initial permutation.

Constraints:

\(1 \le T \le 10\)

\(1 \le N \le 10^5\)

\(1 \le P_i \le N\)