B. Two Arrays Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob have two arrays $$$a,b$$$ of size $$$n$$$ where $$$a_n=b_n$$$.One day,they want to play a game and make a chessboard with $$$2n-1$$$ squares,each with a number (as shown in the following picture) .

Alice has a score $$$s_a$$$ and Bob has a score $$$s_b$$$.At the beginning,$$$s_a$$$ and $$$s_b$$$ are both $$$0$$$.

At the beginning of the game,Alice choose an index $$$i_a(1 \leq i_a \leq n)$$$.After knowing $$$i_a$$$,Bob choose an index $$$i_b(1 \leq i_b \leq n)$$$.And then,Alice and Bob take turns doing some operations, with Alice starting first.

In each turn:

  • if this turn is Alice's,let $$$s_a$$$ increase the number on the grid corresponding to $$$a_{i_a}$$$ and set the number on this grid to $$$0$$$;
  • if this turn is Bob's,let $$$s_b$$$ increase the number on the grid corresponding to $$$b_{i_b}$$$ and set the number on this grid to $$$0$$$;
  • After increasing the score, if the current player's index is less than $$$n$$$, increase the index by $$$1$$$. Otherwise, the current player "stays in place"(do not change the index).

When both players "stay in place", the game ends.

Alice wants to maximize $$$(s_a-s_b)$$$ and Bob wants to minimize $$$(s_a-s_b)$$$.Assuming they all take the best strategy, what is the final value of $$$(s_a-s_b)$$$?

Input

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

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

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

The third line of each testcase contains $$$n$$$ integers $$$b_1,b_2,...,b_n$$$ ($$$1 \leq b_i \leq 10^9$$$,$$$b_n=a_n$$$).

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

Example
Input
3
2
4 1
3 1
2
4 10
3 10
4
1 9 4 5
2 4 3 5
Output
2
7
5
Note

Test case $$$1$$$:

The chessboard is shown in the following picture:

First,Alice chooses $$$i_a=1$$$.After that,Bob chooses $$$i_b=1$$$.

In the first turn,the number on the grid corresponding to $$$a_{i_a}=a_1$$$ is $$$4$$$ .Alice makes $$$s_a$$$ increase by $$$4$$$,sets the number on the grid to $$$0$$$,and increases $$$i_a$$$ by $$$1$$$;

In the second turn,the number on the grid corresponding to $$$b_{i_b}=b_1$$$ is $$$3$$$.Bob makes $$$s_b$$$ increase by $$$3$$$,sets the number on the grid to $$$0$$$,and increases $$$i_b$$$ by $$$1$$$;

In the third turn,the number on the grid corresponding to $$$a_{i_a}=a_2$$$ is $$$1$$$.Alice makes $$$s_a$$$ increase by $$$1$$$,sets the number on the grid to $$$0$$$,and stays in place;

In the fourth turn,the number on the grid corresponding to $$$b_{i_b}=b_2$$$ is already $$$0$$$.Bob makes $$$s_b$$$ increase by $$$0$$$,sets the number on the grid to $$$0$$$,and stays in place.

The final value of $$$s_a-s_b=(4+1)-3=2$$$.It can be proven that they all take the best strategy.

Test case $$$2$$$:

Alice chooses $$$i_a=2$$$ and Bob chooses $$$i_b=1$$$.