## MATH1 - Math I

You are given n integers a_{1}, a_{2},..., a_{n} (0<=a_{i}<=n). The sum a_{1}+ a_{2}+...+ a_{n} does not exceeded n.
Your task is to find n other integers x_{1}, x_{2},..., 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_{1}+ a_{1}= 0) or (x_{n}- x_{1}+ a_{1}= 1) - |x
_{1}|+|x_{2}|+...+|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
_{1}, a_{2},..., a_{n}separated by single spaces

### Output

For each test case output a single value: the minimum value of |x_{1}|+|x_{2}|+...+|x_{n}|

### Example

Input:2 4 2 1 0 0 5 0 1 2 2 0Output:1 3Output Details:In the former case, the optimal solution is (x_{1}=0, x_{2}=0, x_{3}=0, x_{4}=-1) In the latter case, the optimal solution is (x_{1}=-1, x_{2}=-1, x_{3}=0, x_{4}=1, x_{5}=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 |