Yet Another XOR Problem

You are given an integer array $a$ of size $n$. You need to select an integer $K(0\le K < 2^{31})$ and perform the following operation exactly once.

• XOR all the elements of $a$ with $K$. That is, assign $a_i = a_i \oplus K$ for all $1 \le i \le n$, where $\oplus$ is the bitwise xor operator.

Your goal is to make the array non-decreasing.

Output the minimum $K$ and number of possible $K(0 \le K < 2^{31})$ that makes the array non-decreasing.

If it is impossible to find such $K$, output $-1$.

Input

The first line of the input contains a single integer $t(1 \le t \le 10000)$ — the number of test cases.

The first line of each test case contains an integer $n(1 \le n \le 2\times10^5)$ — the number of elements in the array.

The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n (0 \leq a_i < 2^{31})$ — the elements of the array.

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

Output

For each test case, if it is impossible to find such $K$, then output $-1$. Otherwise, print two integers — minimum $K$ and the number of possible $K(0 \le K < 2^{31})$.

Sample

Input	Output
6 2 2 1 2 1 2 1 0 6 6 5 4 3 2 1 4 86 107 101 112 8 113 116 97 101 92 103 107 110	2 1073741824 0 1073741824 0 2147483648 7 268435456 8 268435456 -1
Test case $1$: Minimum $K = 2$. Assign, $a_1 = 2 \oplus 2 = 0$ $a_2 = 1 \oplus 2 = 3$ So, $a_1 \le a_2$. The array is now sorted. Total possible solutions $1073741824$.