Cho 1 dãy \(a\) gồm \(n\) phần tử có thứ tự \(a_1 \le a_2 \le ... \le a_{n-1} \le a_n\)

Có thể thực hiện những thao tác sau trên dãy (\(0\) hoặc nhiều lần):

• Chọn vị trí \(i\) (\(1 \le i \le i_{n-1}\))
• Cộng \(1\) đơn vị vào các phần từ từ \(a_1, a_2,..., a_i\)
• Trừ \(1\) đơn vị vào các phần từ từ \(a_{i+1}, a_{i+2},..., a_n\)

Sau khi thực hiện thao tác thì giá trị của dãy có thể âm.

Xác định số lượng thao tác ít nhất cần thiết để dãy KHÔNG CÒN THỨ TỰ nữa.

Dữ liệu vào: Dòng đầu tiên: số lượng bộ test \(t\) (\(1 \le t \le 100\)). Mỗi bộ test gồm 2 dòng:

• Dòng đầu là số nguyên dương \(n\) (\(2 \le n \le 500\)) cho biết chiều dài của dãy \(a\).
• Dòng thứ ai là \(n\) số nguyên \(a_1\) \(a_2\) ... \(a_{n-1}\) \(a_n\) cách nhau bởi khoảng trắng và \(1 \le a_i \le 10^9\).

Dữ liệu ra:

• Số lượng thao tác ít nhất cần thiết để dãy KHÔNG CÒN THỨ TỰ nữa.

Input

4
2
1 1
4
1 8 10 13
3
1 3 2
3
1 9 14

Output

1
2
0
3

Giải thích

Test 1: Chọn i=1, dãy thành 2 0, không còn thứ tự.
Test 2: Chọn i=3, dãy thành 2 9 11 12. Chọn tiếp i=3, dãy thành 3 10 12 11, không còn thứ tự.