题目描述

给你一个正整数数组 $a_1,a_2,\cdots,a_n$。

你可以将数组中的一些元素涂成红色，但不能有两个相邻的红色元素（即，对于 $1≤i≤n-1$ ，$a_i$ 和 $a_{i+1}$ 中至少有一个不能是红色的）。

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

输入格式

第一行，一个整数 $t$ ($1 \le t \le 500$)，表示有 $t$ 组数据。

对于每组数据，第一行为一个整数 $n$ ($1 \le n \le 100$)，表示有 $n$ 个整数。

第二行为 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示数组。

输出格式

共 $t$ 行：对于每组数据，输出你能得到的最大分数。

translate by

样例

4
3
5 4 5
3
4 5 4
10
3 3 3 3 4 1 2 3 4 5
9
17 89 92 42 29 92 14 70 45

7
6
10
97