每年苹果红了，小A都会在自家院子里的苹果树上摘很多苹果，并把它们随机分成了n堆打包起来，每堆苹果的数量可能相同，也可能不同。
现在，小A需要把这些苹果搬到仓库去，因为小A的力气非常大，他每次可以搬走相邻的两堆苹果，搬走后剩下两边的苹果视作相邻。但他怎么会忘记自己的好朋友小C呢，他想留下苹果数量尽可能多的一堆送给小C。
小A的数学不太好，请你帮帮他。
由于小A喜欢奇数，所以他不会分成偶数堆（即n是奇数）。

第一行包含单个整数t（1<=t<=1000)，表示测试的年数。接下来每个测试包括单个整数n（1<=n<=99,n为奇数），表示该年摘下了n堆苹果，下一行包含 n 个正整数 a₁，a₂，...，a_n( 1≤a_i≤100 )，表示每堆苹果的数量。

对于每年收获苹果的情况，输出一个整数表示每年送给小C的苹果数量。

在第三个样例中，每堆苹果的数量分别是4，7，4，2，9。使剩余最大苹果堆的一种方法是4，7，4，2，9  →  4，2，9  →  9。因此，留下的最大一堆的苹果数量是9。