给定两个长度为 $$$n$$$ 的数组:$$$a_1, a_2, \dots, a_n$$$ 和 $$$b_1, b_2, \dots, b_n$$$。
您可以多次执行以下操作:
1. 选择整数索引 $$$i$$$ ($$$1 \le i \le n$$$);
2. 交换 $$$a_i$$$ 和 $$$b_i$$$。
可能的最小总和 $$$|a_1 - a_2| 是多少+ |a_2 - a_3| + \点 + |a_{n-1} - a_n|$$$ $$$+$$$ $$$|b_1 - b_2| + |b_2 - b_3| + \dots + |b_{n-1} - b_n|$$$ (换句话说,$$$\sum\limits_{i=1}^{n - 1}{\left(|a_i - a_{i+1}| + |b_i - b_{i+1}|\right)}$$$)在执行几次(可能是零)操作后可以实现吗?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 4000$$$) — 测试用例的数量。然后,$$$t$$$ 测试用例如下。
每个测试用例的第一行包含单个整数 $$$n$$$ ($$$2 \le n \le 25$$$) — 数组 $$$a$$$ 和 $$$b$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 数组 $$$a$$$。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — 数组 $$$b$$$。
输出
对于每个测试用例,打印一个整数 - 可能的最小总和 $$$\sum\limits_{i=1}^{n-1}{\left(|a_i - a_{i+1}| + |b_i - b_{i+1}|\right)}$$$。
示例
输入 #1
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
输出 #1
0 8 218
注意
在第一个测试用例中,例如,我们可以将 $$$a_3$$$ 与 $$$b_3$$$ 交换,将 $$$a_4$$$ 与 $$$b_4$$$ 交换。我们将得到数组 $$$a = [3, 3, 3, 3]$$$ 和 $$$b = [10, 10, 10, 10]$$$,总和为 $$$3 \cdot |3 - 3| + 3 \cdot |10 - 10| = 0$$$。
在第二个测试用例中,数组的最小总和(如上所述)已经等于 $$$|1 - 2| + \点 + |4 - 5| + |6 - 7| + \点 + |9 - 10|$$$ $$$= 4 + 4 = 8$$$。
在第三个测试用例中,我们可以例如交换 $$$a_5$$$ 和 $$$b_5$$$。