题目描述

从编号为 $1$～$N$ 的积木中选若干块，堆叠顺序必须按编号递增，且高度为偶数的积木不能放在高度为奇数的积木上。求塔的最大高度。

输入格式

第一行组数 $G$；每组先输入 $N$，随后输入 $N$ 块积木高度。

输出格式

每组输出最大高度。

样例

5
2
4 7
2
7 4
1
7
1
4
7
48 1 50 1 50 1 48

11
7
7
4
196

数据范围

$1\le G\le5$，$1\le N\le50$，$1\le H_i\le50$。