该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

你在玩一个双人游戏。一开始有n个整数在一个数组中，玩家A和B有机会轮流使用它们。每个玩家可以从数组的左端或右端取一个或多个数字，但不能同时从两端取。在他的时间里，他想取多少连续的数字都可以。当玩家从数组中取出所有数字时，游戏结束。

每个玩家的点数是根据他所取的点数的总和来计算的。每个玩家都试图从其他玩家那里获得更多的分数。如果两个玩家都玩得很好，而玩家A开始游戏，那么玩家A比玩家B多多少分?

Format

Input

输入以整数T开始(≤ 100），表示测试用例的数量。 每个案例包含一个空行和一个整数N（1≤ N≤ 100）表示数组的大小。下一行包含N个空格分隔的整数。您可以假设没有任何数字包含超过4位数字。

Output

对于每个测试案例，输出编号和玩家A在游戏结束后获得的最大差值

Samples

2

4
4 -10 -20 7

4
1 2 3 4

Case 1: 7
Case 2: 10

Limitation

1s, 1024KiB for each test case.