J. Stones
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$N$$$ piles of stones appeared in your house, and you need to get rid of as many of them as possible. In the $$$i$$$-th pile, there are $$$b_i$$$ black and $$$w_i$$$ white stones.

You may perform the following operations:

  1. Remove a black stone from a pile. All other piles gain a white stone.
  2. Remove a white stone from a pile. All other piles gain a black stone.
  3. Add a black stone to a pile. All other piles lose a white stone.
  4. Add a white stone to a pile. All other piles lose a black stone.
You are not allowed to perform an operation if it would cause the number of black or white stones in a pile to become negative.

What is the minimum total number of stones you can have after performing these operations?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T (1 \leq T \leq 10)$$$, the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $$$N$$$, $$$(3 \leq N \leq 10^5)$$$ - the number of piles.

The second line of each test case contains $$$N$$$ integers $$$b_1 \dots b_N$$$, $$$(0 \leq b_i \leq 10^9)$$$ - the number of black stones in each pile.

The third line of each test case contains $$$N$$$ integers $$$w_1 \dots w_N$$$, $$$(0 \leq w_i \leq 10^9)$$$ - the number of white stones in each pile.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1-2$$$ satisfy $$$b_1 + b_2 \dots b_N + w_1 + w_2 \dots w_N \leq N-2$$$.

Tests $$$3-7$$$ satisfy $$$b_i = w_i$$$

Tests $$$8-14$$$ satisfy $$$n \leq 10^3, b_i \leq 10^3, w_i \leq 10^3$$$

Tests $$$15-20$$$ satisfy no additional constraints.

Output

For each test case, on a new line, output the minimum number of stones you can have after performing the operations.

Example
Input
4
3
1 1 0
0 0 0
4
4 0 0 0
4 0 0 0
5
1 2 4 3 1
4 2 3 5 1
5
0 0 2 1 1
1 1 2 0 0
Output
1
4
8
5
Note

Problem Idea: Alex_C

Problem Preparation: Alex_C

Occurrences: Advanced J