Alex has a sequence S which contains n elements, let's define f(i, j) denoting the xor sum of Si, Si+1, ..., Sj. Now Alex wants to know the value of f(1, 1) xor f(1, 2) xor ... xor f(1, n) xor f(2, 2) xor f(2, 3) xor ... xor f(2, n) xor ... xor f(n, n).

Input starts with an integer T denoting the number of test case.
For each test case, first line contains an integer n (1 <= n <= 100000).
Next line contains n integers Si(1 <= Si <= 100000).

For each test case. print the value of
f(1, 1) xor f(1, 2) xor ... xor f(1, n) xor f(2, 2) xor f(2, 3) xor ... xor f(2, n) xor ... xor f(n, n).