Cho một bảng giấy gồm ~n~ ô đánh số từ ~1~ tới ~n~. Ban đầu các ô được ghi số ~0~. Bạn được sử dụng các lệnh có dạng ~Fill(i,j,v)~ trong đó ~i,j,v~ là các số nguyên, ~1 \le i \le j \le n~ và ~v \ge 0~ với chức năng như sau:

• Lệnh này chỉ được thực hiện nếu hiện tại số ghi trên tất cả các ô từ ~i~ tới ~j~ đều nhỏ hơn ~v~.

• Khi lệnh này thực hiện, số ~v~ sẽ được ghi vào tất cả các ô từ ~i~ tới ~j~, đè lên số hiện có.

Yêu cầu: Tìm một số ít nhất các lệnh ~Fill~ để điền các số vào bảng giấy sao cho sau khi thực hiện, ta thu được số ghi trên ô ~i~ là ~a_i~.

Input

• Dòng 1 chứa số nguyên dương ~T \le 2 \cdot 10^5~ là số test

• ~T~ nhóm dòng tiếp theo, mỗi nhóm gồm ~2~ dòng chứa dữ liệu một test:

  • Dòng 1 chứa số nguyên dương ~n \le 2 \cdot 10^5~

  • Dòng 2 chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ cách nhau bởi dấu cách ~(0 \le a_i \le 10^9)~

Tổng các giá trị ~n~ trong tất cả ~T~ test không vượt quá ~2 \cdot 10^5~.

Output

Ghi ra ~T~ dòng, mỗi dòng ghi một số nguyên duy nhất là số lệnh ~Fill~ cần thực hiện đối với test tương ứng.

Scoring

Sample Input 1

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 1

2
0
2
4

Notes

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~