MATH1 - Math I

no tags 

You are given n integers a1, a2,..., an (0<=ai<=n). The sum a1+ a2+...+ an does not exceeded n. Your task is to find n other integers x1, x2,..., xn (note that xi may be negative numbers) satisfying the following conditions:

  • (xi - xi+1 + ai+1 = 0) or (xi - xi+1 + ai+1 = 1) for i=1..n-1
  • (xn - x1 + a1 = 0) or (xn - x1 + a1 = 1)
  • |x1|+|x2|+...+|xn| 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 a1, a2,..., an separated by single spaces

Output

For each test case output a single value: the minimum value of |x1|+|x2|+...+|xn|

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)


Added by:Duc
Date:2005-05-25
Time limit:20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET