Trò chơi Điện thoại hỏng

Bối cảnh

Trong trò chơi "Điện thoại hỏng", có tổng cộng N người chơi tham gia. Họ ngồi thành hàng. Khi bắt đầu trò chơi, người chơi đầu tiên nhận một thông điệp bí mật được viết trên một tờ giấy. Sau đó, họ tiếp tục truyền thông điệp bằng cách thì thầm cho người ngồi ngay bên phải mình và tiếp tục như vậy cho đến khi thông điệp đến tay người chơi cuối cùng.

Yêu cầu

Cuối cùng, thông điệp nhận được bởi người chơi cuối cùng được so sánh với thông điệp mà người chơi đầu tiên nói. Nếu các thông điệp không giống nhau, có ai đó đã nghe nhầm thông điệp hoặc truyền lại sai cho người tiếp theo. Nếu thông điệp giống nhau, thì các người chơi thắng và nhận được một món chocolate ngon.

Lưu ý rằng người chơi đầu tiên nhận thông điệp trên tờ giấy, vì vậy họ không thể nghe nhầm.

FullHouse Dev muốn đảm bảo rằng mỗi người chơi đã thực hiện đúng vai trò của mình trong trò chơi, vì vậy ông yêu cầu tất cả mọi người nêu thông điệp mà họ đã nhận được sau khi trò chơi kết thúc. Bạn được cho một mảng A của N số nguyên biểu thị các thông điệp nhận được của mỗi người.

Hãy giúp FullHouse Dev tìm số lượng người chơi có thể đã nghe nhầm thông điệp hoặc truyền lại sai.

Input

Dòng đầu tiên của đầu vào chứa một số nguyên T, biểu thị số lượng test case. Dòng đầu tiên của mỗi test case chứa một số nguyên N, biểu thị số lượng người chơi. Dòng thứ hai chứa N số nguyên cách nhau bởi dấu cách A1, A2, ..., AN, biểu thị các thông điệp của người chơi.

Output

Đối với mỗi test case, xuất một dòng chứa một số nguyên tương ứng với số lượng người chơi có thể đã nghe nhầm thông điệp hoặc truyền lại sai.

Ràng buộc

• \(1 \leq T \leq 5\)
• \(1 \leq A_i \leq 10^9\)
• Subtask 1: 40 điểm
  • \(2 \leq N \leq 10^3\)
• Subtask 2: 60 điểm
  • \(2 \leq N \leq 10^5\)

Ví dụ 1

Input

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

Output

4
3
0

Giải thích ví dụ

• Ví dụ 1: Người chơi thứ 3, thứ 4, thứ 6 và thứ 7 có thể đã nghe nhầm thông điệp hoặc truyền lại sai.
• Ví dụ 2: Ba người chơi đầu tiên có thể đã nghe nhầm thông điệp hoặc truyền lại sai.

Thông tin học tập

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