Niko 正在玩游戏。她的分数由整数 $$$k$$$ 表示,最初为 $$$0$$$。
游戏有 $$$n$$$ 回合。在第 $$$i$$$ 回合,Niko 得到一张上面有整数 $$$a_i$$$ 的红牌,以及上面有整数 $$$b_i$$$ 的蓝牌。她必须准确选择 一 卡片并根据她的选择更新她的分数:
- 如果她选择红牌,她的分数变为 $$$k - a_i$$$,其中 $$$k$$$ 是她在回合前的分数。
- 如果她选择蓝牌,她的分数变为 $$$b_i - k$$$,其中 $$$k$$$ 是她在回合前的分数。
此后,游戏进入下一个回合,如果是第 $$$n$$$ 回合则结束。
你的任务是找到 Niko 在游戏结束时可以获得的最大可能得分。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 匝数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$)。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出一个整数 - Niko 在游戏结束时可以获得的最大可能分数。
示例
输入复制
334 -8 -1-3 -7 05-3 1 0 7 1-5 3 -1 4 -55-7 7 5 4 9-9 -3 3 2 2
输出复制
6 12 27
注意
在第一个测试用例中,一个最佳策略如下:
| 转 | 0 | 1 | 2 | 3 |
| 已选择卡片 | — | 蓝色 | 红色 | 红色 |
| 分数 | $$$0$$$ | $$$-3 - 0 = -3$$$ | $$$-3 - (-8) = 5$$$ | $$$5 - (-1) = 6$$$ |
| 转 | 0 | 1 | 2 | 3 | 4 | 5 |
| 已选择卡片 | — | 蓝色 | 蓝色 | 蓝色 | 蓝色 | 红色 |
| 分数 | $$$0$$$ | $$$-5$$$ | $$$8$$$ | $$$-9$$$ | $$$13$$$ | $$$12$$$ |