时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有一个长度为 \(n\) 的非负整数序列 \(a[1],a[2],…,a[n]\)。每一步你可以从以下三种操作中选择一种执行：

　　选择一个区间 \([l,r]\)，将下标在这个区间里的所有数都减 1。
　　选择一个区间 \([l,r]\)，将下标在这个区间里且下标为奇数的所有数都减 1。
　　选择一个区间 \([l,r]\)，将下标在这个区间里且下标为偶数的所有数都减 1。

　　求最少需要多少步才能将序列中的所有数都变成 0。

【输入格式】

　　第一行输入一个整数 \(T\)，表示数据组数。
　　对于每组数据，第一行输入一个整数 \(n\)，接下来一行输入 \(n\) 个非负整数 \(a[1],a[2],…,a[n]\)。

【输出格式】

　　输出 \(T\) 行，对于每组测试数据，输出一行一个整数，表示答案。

【输入输出样例】

　Input

3
5
2 1 2 1 2
8
1000000000 1000000000 0 1000000000 1000000000 0 1000000000 1000000000
13
1 1 4 5 1 4 1 9 1 9 8 1 0

　Output

2
3000000000
19

【样例解释】

　　第一组数据：
　　21212 ==> 11111 ==> 00000
　　第三组数据：
　　1145141919810 ==> 0034030808700 ==> 0031000000700 ==> 0000000000000

【数据限制】

　　\(对于前 10\%\) 的数据，\(n≤5\)，\(a_i≤10\)。
　　\(对于前 30\%\) 的数据，\(n≤50\)，\(a_i≤50\)。
　　\(对于前 50\%\) 的数据，\(n≤200\)，\(a_i≤200\)。
　　\(对于前 60\%\) 的数据，\(n≤200\)，\(a_i≤10^9\)。
　　\(对于前 70\%\) 的数据，\(n≤1000\)，\(a_i≤10^9\)。
　　\(对于前 90\%\) 的数据，\(n≤10000\)，\(a_i≤10^9\)。
　　\(对于 100\%\) 的数据，\(n≤100000\)，\(a_i≤10^9\)，\(1≤T≤10\)。

【来源】

　　Mr.he