You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Input

The first line contains a single integer $t$ ($1 \le t \le 4000$) — the number of test cases. Then, $t$ test cases follow.

The first line of each test case contains the single integer $n$ ($2 \le n \le 25$) — the length of arrays $a$ and $b$.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the array $a$.

The third line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$) — the array $b$.

Output

For each test case, print one integer — the minimum possible sum $\sum\limits_{i=1}^{n-1}{\left(|a_i - a_{i+1}| + |b_i - b_{i+1}|\right)}$.

3
4
3 3 10 10
10 10 3 3
5
1 2 3 4 5
6 7 8 9 10
6
72 101 108 108 111 44
10 87 111 114 108 100

0
8
218

Note

In the first test case, we can, for example, swap $a_3$ with $b_3$ and $a_4$ with $b_4$. We'll get arrays $a = [3, 3, 3, 3]$ and $b = [10, 10, 10, 10]$ with sum $3 \cdot |3 - 3| + 3 \cdot |10 - 10| = 0$.

In the second test case, arrays already have minimum sum (described above) equal to $|1 - 2| + \dots + |4 - 5| + |6 - 7| + \dots + |9 - 10|$ $= 4 + 4 = 8$.

In the third test case, we can, for example, swap $a_5$ and $b_5$.