Yet Another XOR Problem

Limits 1s, 512 MB

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

Your goal is to make the array non-decreasing.

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

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

Input

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

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

The second line of each test case contains nn space-separated integers a1,a2,,an(0ai<231)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 nn over all test cases does not exceed 5×1055 \times 10^5.

Output

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

Sample

InputOutput
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 11: Minimum K=2K = 2. Assign,

a1=22=0a_1 = 2 \oplus 2 = 0

a2=12=3a_2 = 1 \oplus 2 = 3

So, a1a2a_1 \le a_2. The array is now sorted.

Total possible solutions 10737418241073741824.