You are given n integers a₁, a₂,..., a_n (0<=a_i<=n). The sum a₁+ a₂+...+ a_n does not exceeded n. Your task is to find n other integers x₁, x₂,..., x_n (note that x_i may be negative numbers) satisfying the following conditions:

• (x_i - x_i+1 + a_i+1 = 0) or (x_i - x_i+1 + a_i+1 = 1) for i=1..n-1
• (x_n - x₁ + a₁ = 0) or (x_n - x₁ + a₁ = 1)
• |x₁|+|x₂|+...+|x_n| is minimized

Input

The first line of the input file contains an integer t representing the number of test cases (t<=20). Then t test cases follow. Each test case has the following form:

• The first line contains n (1<=n<=1000)
• The second line contains n integers a₁, a₂,..., a_n separated by single spaces

Output

For each test case output a single value: the minimum value of |x₁|+|x₂|+...+|x_n|

Example

Input:
2
4
2 1 0 0
5
0 1 2 2 0

Output:
1
3

Output Details:
In the former case, the optimal solution is (x1=0, x2=0, x3=0, x4=-1)
In the latter case, the optimal solution is (x1=-1, x2=-1, x3=0, x4=1, x5=0)