Có một băng giấy gồm ~n~ ô, đánh số từ 1 đến ~n~, ban đầu mọi ô đều ghi số 0. Ta được dùng lệnh ~Fill(i, j, v)~ với ~1 \le i \le j \le n~ và ~v \ge 0~ nguyên, hoạt động như sau:

• Lệnh chỉ được thực hiện khi tại thời điểm đó, tất cả các ô từ ~i~ đến ~j~ đều đang ghi số nhỏ hơn ~v~.
• Khi được thực hiện, số ~v~ được ghi đè lên mọi ô từ ~i~ đến ~j~.

Yêu cầu: tìm số lệnh ~Fill~ ít nhất cần dùng để cuối cùng ô ~i~ chứa đúng số ~a_i~ với mọi ~i~.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~T~ (~T \le 2 \times 10^5~), là số bộ test.
• Tiếp theo là ~T~ nhóm, mỗi nhóm gồm 2 dòng:
  • Dòng thứ nhất chứa số nguyên dương ~n~ (~n \le 2 \times 10^5~).
  • Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~ (~0 \le a_i \le 10^9~).

Kết quả

In ra ~T~ dòng, dòng thứ ~i~ là số lệnh ~Fill~ tối thiểu cần dùng cho bộ test thứ ~i~.

Ví dụ

CELLFILL.INP

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

CELLFILL.OUT

2
0
2
4

Giải thích: Với bộ test thứ 4, có thể làm như sau (băng sau mỗi lệnh):

• ~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

Giới hạn

• Subtask 1 (30% số điểm): ~T \le 10~, ~n \le 100~.
• Subtask 2 (30% số điểm): ~T \le 10~, ~n \le 1000~.
• Subtask 3 (40% số điểm): không có ràng buộc thêm.