Description

给定一个长度为 $n$ 的正整数序列 $a_1,\cdots a_n$，你可将序列中的一些元素涂色，但不能有两个相邻的元素同时涂色。

你的得分是涂色元素的最大值加上涂色元素的数量。请求出你能得到的最高分。

Input Format

每组测试包含多个测试用例。第一行包含测试用例的数量 $T$ ( $1\le T\le 500$ )，对于每个测试用例：

• 第一行包含一个整数 $n$ ( $1\le n\le 100$ ) ，表示序列的长度。

• 第二行包含 $n$ 个整数 $a_1,\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