给定一个非负整数序列 $a_1, a_2, \dots, a_n$。你可以执行以下三种操作任意多次：

• 选择一个区间 $[l, r]$，将该区间内所有的数减 1。
• 选择一个区间 $[l, r]$，将该区间内所有奇数下标的数减 1。
• 选择一个区间 $[l, r]$，将该区间内所有偶数下标的数减 1。

输出使所有数变为 0 所需的最少操作次数。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。

对于每个测试用例： 第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。 第二行包含 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)。

输出格式

对于每个测试用例，输出一个整数，表示答案。

样例

样例输入 1

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

样例输出 1

2
3000000000
19