Một dãy gọi là Zigzag nếu \(a_1 < a_2 > a_3 < a_4 \dots\)

Bạn được cho một dãy \(a\) có \(n\) phần tử và bạn được cấp cho \(2\) thao tác:

• Thao tác \(1\): Chọn một phần tử \(a_i\) rồi đổi nó thành \(\max(a_1, a_2, \dots, a_i)\).
• Thao tác \(2\): Chọn một phần tử \(a_i\) rồi trừ nó đi \(1\) đơn vị.

Nhiệm vụ của bạn là tối ưu hóa số lần dùng thao tác \(2\) để dãy \(a\) thành dãy Zigzag, trong khi thao tác \(1\) được sử dụng không giới hạn số lần (miễn phí).

Input

• Dòng đầu tiên chứa số nguyên \(t\) \((1 \le t \le 10^4)\) — số lượng bộ test.
• Mỗi bộ test gồm hai dòng:
  • Dòng thứ nhất chứa số nguyên \(n\) \((1 \le n \le 2 \cdot 10^5)\).
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) \((1 \le a_i \le 10^9)\).
• Tổng các giá trị của \(n\) trên tất cả các bộ test không vượt quá \(2 \cdot 10^5\).

Output

• Với mỗi bộ test, in ra một số nguyên duy nhất là số lượt dùng thao tác \(2\) tối ưu nhất.

Example

7
5
1 4 2 5 3
4
3 3 2 1
5
6 6 6 6 6
7
1 2 3 4 5 6 7
3
3 2 1
2
1 2
9
65 85 19 53 21 79 92 29 96

0
1
3
6
1
0
13

Constraints

• \(1 \le t \le 10^4\)
• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le a_i \le 10^9\)
• Tổng \(n\) trong tất cả các bộ test \(\le 2 \cdot 10^5\)