在参加完一年一度的“双人博弈与应用密码学研讨会”后，Alice 和 Bob 想要通过玩他们最喜欢的游戏来放松一下。他们将 $n$ 片奶酪排成一排，编号从 $1$ 到 $n$。众所周知，虽然奶酪通常都很美味，但有些奶酪比其他的更好——这就是为什么第 $i$ 片奶酪用它的美味值 $o_i$ 来描述。

Alice 先手，双方轮流进行操作。在一次操作中，玩家可以吃掉桌上剩余的任意奶酪集合，前提是该集合中不包含两片相邻的奶酪（即对于任何 $1 \le i \le n-1$，不能同时包含编号为 $i$ 和 $i+1$ 的奶酪）。我们假设奶酪的编号不会改变，因此在游戏过程中不会出现新的相邻对。

当然，两位玩家的目标都是最大化自己吃掉的奶酪的总美味值。假设双方都采取最优策略，Alice 能获得的最高分数是多少？

输入格式

第一行包含测试用例的数量 $z$ ($1 \le z \le 20$)。接下来是各个测试用例，每个测试用例的格式如下：

第一行包含奶酪片数 $n$ ($1 \le n \le 100\,000$)。第二行包含 $n$ 个整数 $o_1, o_2, \dots, o_n$ ($1 \le o_i \le 1\,000\,000$)，表示每片奶酪的美味值。

输出格式

对于每个测试用例，输出一个整数，表示在双方均采取最优策略的情况下，Alice 能吃到的奶酪总美味值。

样例

样例输入 1

2
3
10 10 10
4
1 2 3 4

样例输出 1

20
7