思路：动态规划

状态定义：

考虑 $val[i][0]$ 表示只考虑前 $i$ 个数，第 $i$ 个数，$a_i$ 与 $b_i$ 不交换的情况下，可以获得的相邻数的差值绝对值之和的最大值。
考虑 $val[i][1]$ 表示只考虑前 $i$ 个数，第 $i$ 个数，$a_i$ 与 $b_i$ 交换的情况下，可以获得的相邻数的差值绝对值之和的最大值。

状态转移：

$val[i][0]=\max(val[i - 1][0] + abs(a[i] - a[i - 1]) + abs(b[i] - b[i - 1]), val[i - 1][1] + abs(a[i] - b[i - 1]) + abs(b[i] - a[i - 1]))$

题目内容

小红有两个长度均为 $n$ 数组 $a$ 和 $b$ 。

对于这两个数组，当这两个数组满足 $(\sum\limits_{i=2}^n |a_i-a_{i-1}|) + (\sum\limits_{i=2}^n |b_i-b_{i-1}|)$ 的和最大时，称这两个数组是一个好数组对。

小红允许你交换数组 $a$ 和数组 $b$ 中的任意两个对应位置的元素 $a_i$ 和 $b_i$ 。

现在，小红想问你，最少要交换多少次可以使得这两个数组成为一个好数组对。

输入描述

第一行，一个整数 $T(1\leq T\leq 10)$ ，表示数据组数。 接下来每组数据，

第一行，一个整数 $n(2\leq n\leq 10^5)$ 表示数组大小。

第二行，$n$ 个整数，表示数组 $a$ 的 $n$ 个数，$1\leq a_i\leq 10^9$。

第三行，$n$ 个整数，表示数组 $b$ 的 $n$ 个数，$1\leq b_i\leq 10^9$。

保证 $T$ 组数据所有 $n$ 的和不超过 $10^5$

输出描述

一个整数

样例

输入

1
2
1 2
4 5

输出

1

说明

交换 $a_2$ 和 $b_2$ 。 得到 a = [1, 5], b = [4, 2] 总和为 $6$ ，其余任何方案都不会使得答案大于 $6$