At the Central Bank of Berland, clients store their money and valuables in safe deposit boxes inside a large vault. To enter the vault, a client enters a personal secret code, which consists of $$$n$$$ consecutive non-negative integers.
The bank takes the security of money and valuables very seriously, so it wants clients to change their codes regularly. Some clients do not like changing their codes very much because they keep forgetting them. Forgetful clients make minimal changes to the old code to obtain a new one. To combat this behavior, the bank has made it a paid service to leave a code position unchanged.
Rodion, a regular client of the bank, has his secret code $$$A=[a_1, a_2, \ldots, a_n]$$$ expiring. He has придумал a new secret code $$$B=[b_1, b_2, \ldots, b_n]$$$. The bank's secret code change service works as follows: to transform the old code $$$A$$$ into the new code $$$B$$$, Rodion may perform the following operation any number of times.
Choose an integer $$$k$$$ ($$$0 \le k \lt 40$$$). For each element of the current code $$$A$$$, one of two actions is chosen:
The cost of the operation is the sum of the coins paid for all elements left unchanged in this operation.
Of course, Rodion wants to pay as little as possible for changing the code. Help him find the minimum total cost of operations after which the old code $$$A$$$ becomes equal to the new code $$$B$$$.
If it is impossible to transform code $$$A$$$ into code $$$B$$$, output $$$-1$$$.
The test contains one or more datasets. The first line contains an integer $$$t$$$ — the number of datasets ($$$1 \le t \le 1000$$$). The descriptions of the datasets follow.
The first line of each datasets contains an integer $$$n$$$ — the length of the code ($$$1 \le n \le 2 \cdot 10^5$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, and the third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le a_i, b_i \lt 2^{40}$$$).
The sum of $$$n$$$ over all datasets in one test does not exceed $$$2 \cdot 10^5$$$.
For each dataset, output one integer — the minimum total cost of transforming code $$$A$$$ into code $$$B$$$. If the transformation is impossible, output $$$-1$$$.
4 2 1 7 0 1 3 3 1 4 1 5 9 4 13 10 4 4 1 2 4 4 2 1099511627775 549755813888 7 549755813888
1 -1 6 8
In the first example, the following operations can be performed:
The total cost is $$$1$$$. There is no sequence of operations with smaller cost after which code $$$A$$$ becomes equal to code $$$B$$$.
In the second example, the required transformation is impossible.
| Name |
|---|


