Adjacent Sums

An array A

A of size N(N≥2)

N(N≥2), containing non-negative integers, is called good if all of the following conditions hold:

• A1=A2
• 
  
• A1
• ​=A2
• ​, or A1=0
• 
  
• A1
• ​=0
• AN=AN−1
• 
  
• AN
• ​=AN−1
• ​, or AN=0
• 
  
• AN
• ​=0
• Ai=Ai−1+Ai+1
• 
  
• Ai
• ​=Ai−1
• ​+Ai+1
• ​, or Ai=0
• 
  
• Ai
• ​=0 for all 1<i<N
• 
  
• 1<i<N.

Less formally, we need all non-zero Ai

Ai

​ equal to the sum of it's adjacent elements.

You are given an array A

A of size N

N, consisting of non-negative integers.

In one operation, you can add 1

1 or subtract 1

1 from some element in A

A. It is not allowed to make the elements in A

A negative at any point.

Find the minimum operations to make the array A

A good. It can be proven that it is always possible.

Input Format

• The first line of input will contain a single integer T
• 
  
• T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains N
• 
  
• N - the size of the array A
• 
  
• A.
• The second line contains N
• 
  
• N integers - A1,A2,…,AN
• 
  
• A1
• ​,A2
• ​,…,AN
• ​.

Output Format

For each test case, output on a new line the minimum number of operations to make A

A good.

Constraints

• 1≤T≤104
• 
  
• 1≤T≤104
• 2≤N≤2⋅105
• 
  
• 2≤N≤2⋅105
• 0≤Ai≤109
• 
  
• 0≤Ai
• ​≤109
• The sum of N
• 
  
• N over all test cases does not exceed 2⋅105
• 
  
• 2⋅105
• .

Sample 1:

Input

Output

6 2 0 5 2 3 4 3 0 0 0 3 2 2 1 5 6 7 2 1 2 9 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
5 1 0 1 4 3000000000

Explanation:

Test Case 1 : We can reduce A2

A2

​ by 5

5 to get [0,0]

[0,0] which is good. We could also have increased A1

A1

​ by 5

5 to get [5,5]

[5,5] which is also good.

Test Case 2 : We can reduce A2

A2

​ by 1

1 to get [3,3]

[3,3] which is good.