Nén Video

Bối cảnh

FullHouse Dev đã ghi lại một video giải thích công thức nấu ăn yêu thích của mình. Tuy nhiên, kích thước của video quá lớn để tải lên internet. Anh ấy muốn nén video để nó có kích thước nhỏ nhất có thể.

Yêu cầu

Mô tả

Video của FullHouse Dev ban đầu có N khung hình. Giá trị của khung hình thứ i là Ai. FullHouse Dev có thể thực hiện loại thao tác sau đây bất kỳ số lần nào:

• Chọn một chỉ số i (1 ≤ i ≤ N) sao cho giá trị của khung hình thứ i bằng giá trị của một trong hai khung hình lân cận và xóa khung hình thứ i.

Hãy tìm số khung hình tối thiểu mà FullHouse Dev có thể đạt được.

Input

• Dòng đầu tiên chứa T - số lượng test case.
• Với mỗi test case:
  • Dòng đầu tiên chứa một số nguyên N - số lượng khung hình ban đầu.
  • Dòng thứ hai chứa N số nguyên cách nhau bởi dấu cách, A1, A2, ..., AN - giá trị của các khung hình.

Output

Với mỗi test case, in ra một dòng duy nhất số khung hình tối thiểu mà FullHouse Dev có thể đạt được.

Ràng buộc

• \(1 ≤ T ≤ 1000\)
• \(1 ≤ N ≤ 10^5\)
• \(1 ≤ Ai ≤ 10^6\)
• \(Tổng của N trong tất cả các test case không vượt quá 2⋅10^5.\)

Ví dụ 1

Input

4
1
5
2
1 1
3
1 2 3
4
2 1 2 2

Output

1
1
3
3

Giải thích ví dụ

Test case 1: Chỉ có một khung hình với giá trị 5. Vì không có khung hình lân cận, FullHouse Dev không thể xóa khung hình nào và số khung hình tối thiểu là 1.

Test case 2: Có hai khung hình, cả hai đều có giá trị 1. FullHouse Dev có thể xóa khung hình đầu tiên vì giá trị của nó bằng giá trị của khung hình thứ hai. Khung hình còn lại có giá trị [1]. Số khung hình tối thiểu là 1.

Test case 3: Có 3 khung hình. Tất cả các khung hình đều có giá trị khác nhau. Do đó, số khung hình tối thiểu là 3.

Test case 4: FullHouse Dev có thể xóa khung hình thứ tư vì giá trị của nó bằng giá trị của khung hình thứ ba. Các khung hình còn lại có giá trị [2,1,2]. Do đó, số khung hình tối thiểu là 3.

Thông tin học tập

• Buổi: B09
• Concepts: 1D arrays, consecutive-group counting
• Giới hạn kiến thức: B01-B09
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 20