Harasees has an array A of size N containing non-negative integers. He starts at the index 1 of A and wants to reach the index N. In one move, he can do the following:
If he is currently at index i, then he can move to any index j such that i ≤ j ≤ $\min(i + A_{i}, N)$.

The cost of a path is defined as the [bitwise OR] of all the array elements visited by Harasees during his journey from index 1 to N. Formally if he visited the indices $1, X_{1}, X_{2}, \ldots, X_{K}, N$, then the cost of this path = (A_{1} \ | \ A_{X_{1}} \ | \ A_{X_{2}} \ | \ $\ldots$ \ | \ A_{X_{K}} \ | \ A_{N}).

Determine the minimum possible cost to reach index N from index 1. If it is not possible to do so, output -1.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains a single integer N - the length of the array A.
• The next line contains $N space-separated integers A_{1}, A_{2}, \dots, A_{N}$ denoting the array A.

------ Output Format ------

For each test case, output the minimum cost to go from index 1 to index N using the given moves. If it is not possible to do so, output -1.

------ Constraints ------

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 5 \cdot 10^{5}$
$0 ≤ A_{i} ≤ 5 \cdot 10^{5}$
- The sum of $N$ over all test cases won't exceed $5 \cdot 10^{5}$.

------ subtasks ------

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------
2
5
1 1 1 1 1
4
2 4 1 3
----- Sample Output 1 ------
1
3
----- explanation 1 ------
- Test Case 1: Harasees has no choice but to keep going from his current position to the position that follows it immediately till he reaches the $5$th index. So the minimum cost (in this case, the only possible cost) is $1\ |\ 1\ |\ 1\ |\ 1\ |\ 1\ =\ 1$.
- Test Case 2: It is optimal for Harasees to make the following moves: $(i = 1) \rightarrow (i = 3) \rightarrow (i = 4)$. The cost of this path is: $A_{1} \ | \ A_{3} \ | \ A_{4} = 2\ |\ 1\ |\ 3\ =\ 3$. We can prove that no path exists with a cost $< 3$.

----- Sample Input 2 ------
1
5
1 0 2 3 3
----- Sample Output 2 ------
-1
----- explanation 2 ------
- Test Case 1: In this case Harasees will get stuck at index $2$ and there is no way to reach the last index.

见题面

见题面