There is a giant circular container which is divided into N segments numbered from 0 to N-1.

Each segment has two bottles, one is a bottle of cold drink and other is a bottle of poison. Drinking from bottle of cold drink increases your energy by A[i] while drinking from bottle of poison decreases your energy by B[i].

The corresponding energies for the same are given in input.

Now as it is circular, so bottles in segment N-1 and segment 0 are adjacent. If you do not drink from bottle of cold-drink, then you have to drink from bottle of poison in that segment. Furthermore you cannot drink from bottle of cold-drink in adjacent segments. You have to drink in such a way so that your energy maximizes. Find this maximum value.

Note: Your initial energy will be 0 and the final maximum energy can be negative.

Input

There will be T test cases and in each test case there will be an integer N which is the size of the container.

Next line contain N integers denoting the first array and the second line also contain N integers denoting the second array.

Output

There will be T lines each containing the output for each test case.

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 10000
1 ≤ A[i], B[i] ≤ 10⁹

Sample

Input:
1
3
1 2 3
4 5 6
Output:
-6

Explanation

There are 3 segments and the pairs are (1, 4), (2, 5), (3, 6). The optimal solution is to drink third potion and first two bottle of poison. The answer in this case is (-4 + - 5 + 3 ) = -6.