Bob likes sequences.
There is a sequence of non-negative integers $a_1, a_2, \dots, a_n$ of length $n$. In each step, you can choose one of the following three operations to perform:
- Choose an interval $[l, r]$ and decrease all numbers with indices in this interval by 1.
- Choose an interval $[l, r]$ and decrease all numbers with odd indices in this interval by 1.
- Choose an interval $[l, r]$ and decrease all numbers with even indices in this interval by 1.
Find the minimum number of steps required to make all numbers in the sequence 0.
Input
The first line contains an integer $T$, representing the number of test cases.
For each test case, the first line contains an integer $n$, and the next line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$.
Output
Output $T$ lines, each containing a single integer representing the answer for the corresponding test case.
Examples
Input 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
Output 1
2 3000000000 19
Note
First test case: $21212 \xrightarrow{1} 11111 \xrightarrow{1} 00000$
Third test case: $1145141919810 \xrightarrow{1} 0034030808700 \xrightarrow{8} 0031000000700 \xrightarrow{10} 0000000000000$
Constraints
- For the first 10% of the data, $n \le 5, a_i \le 10$.
- For the first 30% of the data, $n \le 50, a_i \le 50$.
- For the first 50% of the data, $n \le 200, a_i \le 200$.
- For the first 60% of the data, $n \le 200, a_i \le 10^9$.
- For the first 70% of the data, $n \le 1000, a_i \le 10^9$.
- For the first 90% of the data, $n \le 10000, a_i \le 10^9$.
- For 100% of the data, $1 \le n \le 100000, 0 \le a_i \le 10^9, 1 \le T \le 10$.