问题描述

やまい ゆづる和やまい かぐや（如果你不认识她们请当作小A和小B）已经经行了98场决斗，现在要进行的第99场是一场关于博弈的。她们要从一个给定的有n（n<= 1000）个数的序列中取数，每次只能从左端或右端取若干个数（至少一个），但不能两端都取，所有数都被取走后，两人分别统计所取数的和作为各自的得分。やまい ゆづる先手，她想知道她可不可以获胜（如果她预先知道了她会输她就会耍赖皮的），你最后只需输出やまい ゆづる的最大分数。由于她们已经进行了太多场比赛，所以两个人都非常的聪明。

输入格式

第一行，一个正整数T，表示有T组数据。（T<=100） 接着T行，每行第一个数为n，接着n个整数表示给定的序列.

输出格式

输出T行，每行一个整数，表示やまい ゆづる每次的得分

输入样例

2
1 -1
2 1 2

输出样例

-1
3

时限

4s.

福利：前两个数据非常的弱。并且全部是随机数据。