Cho một mảng gồm \(N\) phần tử \(A[1],A[2],...,A[N]\) với \(A[i]\in \left\{0,1\right\}\text{ }\forall 1\le i\le N\) và ta có một phép toán sau:

• Chọn \(j(1\le j\le n)\) bất kì và gán \(A[j]=1-A[j]\)

Hỏi ta cần thực hiện ít nhất bao nhiêu phép toán để mảng trên chứa các phần tử \(0,1\) xen kẻ nhau.

Input

• Dòng thứ nhất chứa số nguyên \(T(1\le T\le 100)\)- Thể hiện số lượng testcase.
• Ứng với mỗi testcase, sẽ là một block có dạng như sau:
• Dòng thứ nhất chứa số nguyên \(N(1\le N\le 10000)\)
• Dòng thứ hai chứa \(N\) số nguyên \(A[i](1\le i\le n)\) với \(A[i]\in \left\{0,1\right\}\)

Output

• Ứng với mỗi testcase, in ra kết quả cần tìm tương ứng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1\le N\le 200\)
• Subtask \(2\) (\(80\%\) số điểm): \(1\le N\le 10000\)

Example

3
3
0 0 0
3
0 1 0
3
1 1 1   

1
0
1