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

Explanation

In the former case, the optimal solution is (x₁=0, x₂=0, x₃=0, x₄=-1)

In the latter case, the optimal solution is (x₁=-1, x₂=-1, x₃=0, x₄=1, x₅=0)