题目描述

桌子上从左到右放着 $n$ 个糖果。糖果从左到右编号。第 $i$ 颗糖果的重量为 $w_i$。熊大和熊二吃糖果。

熊大可以从左边吃任意数量的糖果（他必须连着吃，不能跳过糖果）。

熊二可以从右边吃任意数量的糖果（他必须连着吃，不能跳过糖果）。

作为好兄弟，他们希望公平，即目标是吃同样重量的糖果。他们总共最多能吃多少个糖果？

输入格式

第一行包含整数 $t(1≤t≤10^4)$，表示测试用例数。

每个测试用例的第一行包含一个整数 $n(1≤n≤2\times10^5)$，表示桌上糖果的数量。

每个测试用例的第二行包含 $n$ 个整数 $w_1,w_2,…,w_n(1≤w_i≤10^4)$，表示从左到右的糖果重量。

保证所有测试用例的 $n$ 之和不超过 $2\times10^5$。

输出格式

对于每个测试用例，输出一个整数，熊大和熊二在满足条件的情况下总共可以吃的糖果的最大数量。

测试样例

4
3
10 20 10
6
2 1 4 2 4 1
5
1 2 4 8 16
9
7 3 20 5 15 1 11 8 10

2
6
0
7

样例说明

对于第一个测试用例，熊大将从左边吃一颗糖果，熊二将从右边吃一颗。没有更好的方法来吃到同样的重量。答案是 $2$，因为他们总共吃了两颗糖。

对于第二个测试用例，熊大将吃左边的前三颗糖果（总重量 $7$），熊二将吃右边的前三粒糖果（总重量 $7$）。他们不能吃更多的糖果，因为所有的糖果都吃过了，所以答案是 $6$（因为他们总共吃了六颗糖果）。

对于第三个测试用例，熊大和熊二不可能吃相同的重量，因此答案为 $0$。

对于第四个测试案例，熊大将吃重量为 $[7,3,20]$ 的糖果，熊二将吃重量 $[10,8,11,1]$ 的糖果，他们每人吃 $30$ 的重量。没有更好的方案，所以答案是 $7$。