E. Power and Modulo
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Given $$$n$$$ non-negative integers $$$A_1, A_2, \cdots, A_n$$$. Determine if there is only one positive integer $$$M$$$ that $$$\forall i \in \{1, 2, \cdots, n\},\, A_i = 2^{i-1} \!\!\mod M$$$. If so, print the integer $$$M$$$, or print "-1".

Here, $$$a \!\!\mod b$$$ denotes the remainder of $$$a$$$ after division by $$$b$$$, where $$$a \in [0,b)$$$ holds. For example, $$$5 \!\!\mod 2 = 1$$$, $$$9 \!\!\mod 3 = 0$$$, $$$1 \!\!\mod 2 = 1$$$.

Input

The first line contains one integer $$$T\,(1\le T \le 10^5)$$$, denoting the number of test cases.

For each test case:

The first line contains one integer $$$n\,(1\le n \le 10^5)$$$, denoting the number of given integers.

The second line contains $$$n$$$ integers $$$A_1, A_2, \cdots, A_n \,(0 \le A_i \le 10^9)$$$, denoting the given integers.

It is guaranteed that $$$\sum n \le 10^5$$$ among all cases.

Output

For each test case:

Output one line containing one integer, denoting the answer.

Example
Input
3
5
1 2 4 1 2
5
1 2 4 8 16
5
1 2 4 0 1
Output
7
-1
-1
Note
  • For the first test case, $$$M = 7$$$.
  • For the second test case, $$$M$$$ can be any integer greater than 16, so output "-1" here.
  • For the third test case, no valid $$$M$$$ exists.