题目描述

圣诞节要到了，老师要打扮成圣诞老人给同学们分糖果，老师决定先分给第一小组的4名同学，如果每人分4个糖果还多1个，老师这次准备了多少个糖果呢？这是一道小学问题，但本题有着更为复杂的情况，你能帮忙解决吗

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

例如孩子们的表现为 [1,0,2] 你可以分别给这三个孩子分发 2、1、2 颗糖果，共 5 颗糖果。

输入格式

输入包含多行数据，第一行为 \(T\)，接下来的 \(T\) 组数据每组输入一个 \(N\)，然后输入 \(N\) 个数，分别表示这 \(N\) 个孩子的表现，每个数以空格分隔。

0 < T <= 30
0 < N <= 20000

输出格式

针对每组数据输出一个答案表示老师分发的糖果数量。

样例

样例输入

2
3
1 0 2
3
1 2 2

样例输出

5
4