E. And Constraint
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
wowaka & Hatsune Miku - Tosenbo

You are given a sequence $$$a$$$ of length $$$n-1$$$ and a sequence $$$b$$$ of length $$$n$$$.

You can perform the following operation any number of times (possibly zero):

  • choose an index $$$1 \le i \le n$$$ and increment $$$b_i$$$ by $$$1$$$ (i.e., set $$$b_i \leftarrow b_i + 1$$$).

Your goal is to perform the minimum number of operations such that for every $$$1 \le i \le n-1$$$, the condition $$$b_i \, \& \, b_{i+1} = a_i$$$ holds, where $$$\&$$$ denotes the bitwise AND operation. If it is impossible to satisfy the condition, report it as well.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

The second line contains $$$n-1$$$ integers $$$a_1, a_2, \ldots, a_{n-1}$$$ ($$$0 \le a_i \lt 2^{29}$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \lt 2^{29}$$$).

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

Output

For each test case, you need to output only one integer.

If the goal can be achieved, output one integer — the minimum number of operations required. Otherwise, output $$$-1$$$.

Example
Input
7
4
1 4 4
1 2 3 4
4
4 0 4
1 1 1 1
2
1
0 0
3
1 1
0 1 2
6
1 2 3 4 5
1 1 4 5 1 4
2
0
0 0
4
0 1 0
536870911 536870911 536870911 536870911
Output
4
-1
2
2
-1
0
536870916
Note

In the first test case, one of the optimal strategies is to use $$$4$$$ operations to make $$$b = [1,5,4,4]$$$, which satisfies all the conditions. We can prove that it is impossible to use fewer than $$$4$$$ operations.

In the second test case, since $$$b_1 \, \& \, b_2 = 4$$$ and $$$b_2 \, \& \, b_3 =0$$$, then $$$b_3 \, \& \, 4 =0$$$. However, we require that $$$b_3 \, \& \, b_4 =4$$$, which means it is impossible to satisfy all the conditions.