Alice 和 Bob 喜欢玩游戏。今天，他们在 2 行 $n$ 列的特殊网格上进行游戏。Alice 和 Bob 各有一个棋子，分别起始于 $(1, 1)$ 和 $(2, n)$。他们轮流移动自己的棋子，Alice 先手。

在每一回合中，他们可以选择原地不动，或者将棋子移动到水平或垂直相邻且未被对方棋子访问过的点。游戏将在 $10^{10}$ 回合后结束。

网格中的每个点都有一个非负权重。对于每位玩家，其得分为其棋子所访问过的所有点的权重之和。权重仅计算一次，即使棋子多次访问同一个点。

Alice 和 Bob 都希望最大化自己的得分。作为旁观者，请计算在双方均采取最优策略的情况下，Alice 的得分。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 5 \cdot 10^4$)。接下来是各测试用例。

每个测试用例的第一行包含一个整数 $n$，表示网格的大小 ($1 \le n \le 10^5$)。

第二行包含 $n$ 个整数 $a_{1,1}, a_{1,2}, \dots, a_{1,n}$，其中第 $i$ 个数表示点 $(1, i)$ 的权重。

第三行包含 $n$ 个整数 $a_{2,1}, a_{2,2}, \dots, a_{2,n}$，其中第 $i$ 个数表示点 $(2, i)$ 的权重。

保证 $0 \le a_{i,j} \le 10^9$，且所有测试用例的 $n$ 之和不超过 $2.5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示在双方均采取最优策略的情况下，Alice 的得分。

样例

样例输入 1

4
2
1 4
2 1
3
1 1 4
5 1 4
4
1 9 4 9
1 0 0 1
7
3 1 4 1 5 9 2
6 5 3 5 8 9 8

样例输出 1

5
6
15
25