考虑一个由层组成的无限三角形。让我们从三角形的顶部(从上到下)对层进行编号,从一层开始。三角形的第 $$$k$$$ 层包含 $$$k$$$ 点,从左到右编号。无限三角形的每个点都由一对数字 $$$(r, c)$$$ ($$$1 \le c \le r$$$) 描述,其中 $$$r$$$ 是层的编号,$$$c$$$ 是层中点的编号。从每个点 $$$(r, c)$$$ 到点 $$$(r+1, c)$$$ 和 $$$(r+1, c+1)$$$ 有两条有向边,但只有其中一条边被激活。如果 $$$r + c$$$ 是偶数,则激活到点 $$$(r+1, c)$$$ 的边缘,否则激活到点 $$$(r+1, c+1)$$$ 的边缘。查看图片以更好地理解。
激活的边缘显示为黑色。未激活的边缘呈灰色。
从点 $$$(r_1, c_1)$$$ 可以到达点 $$$(r_2, c_2)$$$,如果它们之间仅存在来自激活边的路径。例如上图中,有一条从 $$$(1, 1)$$$ 到 $$$(3, 2)$$$ 的路径,但没有从 $$$(2, 1)$$$ 到 $$$(1, 1)$$$ 的路径。
最初,您位于 $$$(1, 1)$$$ 点。对于每一回合,您可以:
- 替换点 $$$(r, c)$$$ 的激活边。也就是说,如果到点 $$$(r+1, c)$$$ 的边被激活,则到点 $$$(r+1, c+1)$$$ 的边被激活,否则,如果到点 $$$(r+1, c+1)$$$ 的边被激活,则到点 $$$(r+1, c)$$$ 的边被激活。此操作使路径成本增加$$$1$$$;
- 沿着激活的边缘从当前点移动到另一个点。此操作不会增加路径的成本。
给你一个无限三角形 $$$(r_1, c_1), (r_2, c_2), \ldots, (r_n, c_n)$$$ 的 $$$n$$$ 点序列。找到从 $$$(1, 1)$$$ 开始的最小成本路径,以任意顺序经过所有 $$$n$$$ 点。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) 是测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例都以包含一个整数的行开头 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) 是要访问的点的数量。
第二行包含$$$n$$$数字$$$r_1, r_2, \ldots, r_n$$$ ($$$1 \le r_i \le 10^9$$$),其中$$$r_i$$$是第$$$i$$$个点所在层的编号。
第三行包含 $$$n$$$ 数字 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le r_i$$$),其中 $$$c_i$$$ 是 $$$r_i$$$ 层中第 $$$i$$$ 点的编号。
保证所有 $$$n$$$ 点都是不同的。
保证至少有一种方法可以遍历所有 $$$n$$$ 点。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出通过相应测试用例中所有点的路径的最小成本。
示例
输入 #1
4 3 1 4 2 1 3 1 2 2 4 2 3 2 1 1000000000 1 1000000000 4 3 10 5 8 2 5 2 4
输出 #1
0 1 999999999 2