Description

给定一个长度为$n$的正整数数组 $a_1,a_2,a_3,\cdots a_n$。 你可以将数组中的一些元素涂成红色，但不能有两个相邻的红色元素(即对于 $1\le i\le n−1$ 来说，$a_i$ 和 $a_{i+1}$ 中至少有一个元素不是红色的)。 您的得分是红色元素的最大值加上红色元素的数量。请找出您能得到的最高分。

Input Format

每个测试包含多个测试用例。第一行包含测试用例的数量 $T$ ( $1\le T\le 500$ )。测试用例说明如下。

每个测试用例的第一行都包含一个整数 $n$ ( $1\le n\le 100$ ) - 数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n$ ( $1\le a_i\le 1000$ ) - 给定的数组。

Output Format

对于每个测试用例，输出一个整数：将某些元素染成红色后可能得到的最大分数。

3
4
5 4 5 2
3
5 10 2
5
1 4 2 3 2

7
11
6