Statement
Thanh 想要在一面长度为 N 的墙上画一幅精美的壁画。墙的每一段都有一个*美丽分数*，表示如果涂上颜料后看起来有多美。
不幸的是，由于最近的一场洪水，墙开始坍塌，所以他需要快速工作！
每天开始时，Thanh 会涂刷墙的一段。第一天，
他可以自由选择任何一段涂刷。在之后的每一天，他必须涂刷一段新的、
与他已经涂刷过的某段相邻的段，因为他不想分裂壁画。
每天结束时，墙的一段会被摧毁。
被摧毁的总是仅与另一段相邻且未涂刷的段
（Thanh 使用的是防水颜料，所以涂刷过的段不会被摧毁）。
Thanh 壁画的*总美丽值*等于他涂刷过的所有段的美丽分数之和。
Thanh 希望保证，无论墙如何被摧毁，他仍然能达到至少 B 的总美丽值。
他能保证达到的最大 B 值是多少？
Input
输入的第一行给出测试用例的数量 T。接下来有 T 个测试用例。
每个测试用例以一行包含整数 N 开始。然后下一行包含
一个由 N 个 0 到 9 的数字组成的字符串。第 i 个数字表示墙的第 i 段的美丽分数。
### 数据范围
- 1 ≤ T ≤ 100.
- 2 ≤ N ≤ 100.
- 对于恰好 1 个测试用例，N = 5 × 10；对于其他 T - 1 个测试用例，
Output
对于每个测试用例，按测试用例顺序逐个输出答案，每个测试用例输出一行包含 y，其中 y 是 Thanh 能够保证达到的最大美丽分数，如上所述。
Examples
Input
4
4
1332
4
9583
3
616
10
1029384756Output
6
14
7
31Constraints
- Time limit: 10000 ms
- Memory limit: 1048576 KB
- Tag: greedy
- Tag: math
- Tag: prefix-sum