Một dãy số \(a_1,\ a_2,\ldots,\ a_n\) được gọi là dãy số tốt khi và chỉ khi mọi đoạn con \([l,\ r]\) của nó (\(1\leq l\leq r\leq n)\) đều thỏa mãn điều kiện: \(a_l+a_{l+1}+\ldots+a_r=\frac{1}{2}(a_l+a_r)\cdot(r-l+1)\).

Bạn có thể thực hiện một số thao tác, mỗi thao tác thay thế một phần tử bất kỳ trong mảng thành một số thực bất kỳ (chú ý không thay đổi vị trí đứng của nó). Nhập vào một dãy số \(a\), tìm số thao tác tối thiểu cần thực hiện để biến dãy \(a\) thành dãy số tốt.

Input

• Dòng đầu chứa một số nguyên dương \(T\ (1\leq T\leq100)\): số lượng test cases;
• Mỗi dòng trong số \(T\) nhóm dòng tiếp theo thể hiện một truy vấn;
• Dòng đầu tiên của mỗi truy vấn chứa một số nguyên dương \(n\ (1\leq n\leq70)\): kích thước của dãy \(a\);
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,\ a_2,\ldots,\ a_n\ (-100\leq a_i\leq100)\).

Output

• Với mỗi test case, in ra một số nguyên dương duy nhất là số thao tác ít nhất cần thực hiện để biến dãy số đã cho thành dãy số tốt.

Ví dụ

Sample input

5
4
1 2 3 4
4
1 1 2 2
2
0 -1
6
3 -2 4 -1 -4 0
1
-100

Sample output

0
2
0
3
0

Note

• Ở test case thứ nhất, thứ ba và thứ năm, dãy số đã cho đã là dãy số tốt;
• Ở test case thứ hai, ta có thể thao tác trên hai phần tử cuối cùng để dãy thành dãy số tốt: \([1,\ 1,\ 1,\ 1]\);
• Ở test case thứ tư, ta lần lượt thao tác với các phần tử ở vị trí \(1,\ 3,\ 5\) để biến dãy số thành: \([-2.5,\ -2,\ -1.5,\ -1,\ -0.5,\ 0]\).