Cho một băng giấy gồm n ô, được đánh số từ 1 đến n. Ban đầu, tất cả các ô đều được ghi số 0.

Bạn được phép sử dụng các lệnh có dạng: Fill(i, j, v) , trong đó i, j, v là các số nguyên thỏa mãn: 1 ≤ i ≤ j ≤ n, v ≥ 0.

Lệnh Fill(i, j, v) được thực hiện theo quy tắc sau:

• Lệnh chỉ được thực hiện nếu hiện tại số ghi trên tất cả các ô từ i đến j đều nhỏ hơn v;
• Khi lệnh được thực hiện, số v được ghi vào tất cả các ô từ i đến j, thay thế các giá trị hiện có.

Yêu cầu: Tìm số lượng lệnh Fill ít nhất cần thực hiện để cuối cùng số ghi trên ô thứ i đúng bằng aᵢ với mọi 1 ≤ i ≤ n.

INPUT

Dòng đầu tiên chứa số nguyên dương T (T ≤ 2 × 10⁵) là số lượng test.

Mỗi test gồm 2 dòng:

• Dòng thứ nhất chứa số nguyên dương n (n ≤ 2 × 10⁵);
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ (0 ≤ aᵢ ≤ 10⁹).

Tổng các giá trị n của tất cả các test không vượt quá 2 × 10⁵.

OUTPUT

Ghi ra T dòng.

Mỗi dòng chứa một số nguyên duy nhất là số lệnh Fill ít nhất cần thực hiện đối với test tương ứng.

Ràng buộc

Subtask 1 — 30% : T ≤ 10, n ≤ 100.

Subtask 2 — 30% : T ≤ 10, n ≤ 1000.

Subtask 3 — 40% : Không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề.

Ví dụ

Sample Input

4
6
0 1 2 2 2 1
4
0 0 0 0
8
2 2 2 3 3 3 3 3
9
0 1 1 2 3 2 1 2 1

Sample Output

2
0
2
4

Giải thích

Test 4

• Fill(2, 9, 1) : 0 1 1 1 1 1 1 1 1

• Fill(4, 6, 2) : 0 1 1 2 2 2 1 1 1

• Fill(5, 5, 3) : 0 1 1 2 3 2 1 1 1

• Fill(8, 8, 2) : 0 1 1 2 3 2 1 2 1