题目描述

乔治喜欢玩积木。目前他有N 块积木，编号为1 到N。所有积木的高度都是正整数，第i 块积木高度是H[i]。乔治喜欢用积木堆起尽可能高的塔。他堆积木的过程中，只需要同时满足如下三个规则：

（1）积木必须堆放在同一个列中，一个搭在另一个上面。最终的塔的高度就是构成塔的所

有积木的高度总和。

（2）塔中使用的积木的编号从底部到顶部必须是递增的。换句话说，每当乔治把积木x 放

在积木y 的上面，必须要满足编号x 大于 编号y。

（3）乔治永远不会把高度是偶数的积木放置在高度是奇数的积木上面。

在满足上面的前提下，塔最高是多高？

输入格式

多组测试数据。

第一行，一个整数G，表示有G 组测试数据。1 <= G <= 5。

每组测试数据格式如下：

第1 行，一个正整数N。 2 <= N <= 50。

第2 行，N 个正整数，空格分开，第i 个整数就是编号为i 的积木的高度H[i]，

1 <= H[i] <= 50。

输出格式

共G 行，每行一个正整数。

样例

输入

5
2
4 7
2
7 4
1

输出

7
1
4
7
48 1 50 1 50 1 48
11
7
7
4
196

提示

对于第5 组测试数据的解释：

从底部往顶部，依次选择第1、第3、第5、第7 块积木，这样塔的高度是：

48+50+50+48=196。