H. Hard Problem
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a sequence of nonnegative integers $$$a_1, a_2, \ldots, a_n$$$. You can perform the following three types of operations any number of times.

  • Choose an interval $$$[l, r]$$$, decrease all numbers in the interval by $$$1$$$.
  • Choose an interval $$$[l, r]$$$, decrease all numbers with odd indices in the interval by $$$1$$$.
  • Choose an interval $$$[l, r]$$$, decrease all numbers with even indices in the interval by $$$1$$$.

Output the minimum number of operations to make all numbers equal to $$$0$$$.

Input

In the first line, $$$T$$$ ($$$1\leq T \leq 10$$$) — the number of test cases.

For each test case:

  • In the first line, $$$n$$$ ($$$1\leq n \leq 10^5$$$).
  • In the second line, $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i\leq 10^9$$$).
Output

For each test case, one integer — the answer.

Example
Input
3
5
2 1 2 1 2
8
1000000000 1000000000 0 1000000000 \
1000000000 0 1000000000 1000000000
(There won’t be extra line breakers \
in the actual test cases.)
13
1 1 4 5 1 4 1 9 1 9 8 1 0
Output
2
3000000000
19