小苯有一个长度为 的数组 ，但 中可能存在一些负数会使得 的总和不够大。 现在小苯希望 的总和（即：）尽可能大，为此他可以做如下操作任意次（两种都任意次）： 选择两个相邻的数字 和 ，将其删除，其余数字顺次拼接起来。（换句话说操作后 数组变为：。） 选择三个连续的数字 和 ，将其删除，其余数字拼接起来。（换句话说操作后 数组变为：。） 以上操作小苯均可执行任意次，他想知道数组 的最大总和可以达到多少，请你帮他算一算吧。

输入描述:

本题有多组测试数据。输入的第一行包含一个正整数 ，表示数据组数。接下来包含 组数据，每组数据的格式如下：第一行一个正整数 ，表示数组 的初始长度。第二行 个整数 ，表示数组 。（保证所有测试数据中， 的总和不超过 。）

输出描述:

对于每组测试数据：在单独的一行输出一个整数，表示数组 的最大总和。