Bob 喜欢序列。

有一个长度为 $n$ 的非负整数序列 $a_1,a_2,\dots ,a_n$。每一步你可以从以下三种操作中选择一种执行：

• 选择一个区间 $[l,r]$，将下标在这个区间里的所有数都减 $1$。

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

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

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

输入格式

第一行输入一个整数 $T$，表示数据组数。

对于每组数据，第一行输入一个整数 $n$，接下来一行输入 $n$ 个非负整数 $a_1,a_2,\dots ,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

explanation

第一组数据：$21212\stackrel{1}{\to }11111\stackrel{1}{\to }00000$

第三组数据：$1145141919810\stackrel{1}{\to }0034030808700\stackrel{8}{\to }0031000000700\stackrel{10}{\to }0000000000000$

样例二

见附加文件中 ex_seq2.in 与 ex_seq2.ans。

限制与约定

对于前 $10\mathrm{\%}$ 的数据，$n\le 5,a_i\le 10$。

对于前 $30\mathrm{\%}$ 的数据，$n\le 50,a_i\le 50$。

对于前 $50\mathrm{\%}$ 的数据，$n\le 200,a_i\le 200$。

对于前 $60\mathrm{\%}$ 的数据，$n\le 200,a_i\le {10}^9$。

对于前 $70\mathrm{\%}$ 的数据，$n\le 1000,a_i\le {10}^9$。

对于前 $90\mathrm{\%}$ 的数据，$n\le 10000,a_i\le {10}^9$。

对于 $100\mathrm{\%}$ 的数据，$1\le n\le 100000,0\le a_i\le {10}^9,1\le T\le 10$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载