Trò chơi xếp hình

Tí có một bộ đồ chơi xếp hình gồm $n$ miếng ghép hình tam giác vuông cân được đánh số thứ tự từ $1$ đến $n$, với độ dài cạnh góc vuông là $1$ đơn vị. Mỗi miếng ghép có một màu xác định. Hai miếng ghép cùng màu có thể ghép lại thành một hình vuông với độ dài cạnh là $1$ đơn vị.

Tí cần chọn ra một dãy liên tiếp $(2\times k)+1$ $(k\ge 0)$ miếng ghép trong số $n$ miếng ghép đã cho, trong đó $2\times k$ miếng ghép được dùng để ghép thành $k$ hình vuông. Sau đó, Tí xếp chồng các hình vuông này thành một tòa tháp nhiều tầng, miếng ghép cuối cùng dùng làm mái.

Yêu cầu: Đếm số tầng nhiều nhất có thể của một tòa tháp hợp lệ mà Tí có thể xếp được.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương $t$ $(1\le t\le 100)$ là số bộ dữ liệu. Tiếp theo là $t$ nhóm dòng, mỗi nhóm dòng mô tả một bộ dữ liệu với cấu trúc:

• Dòng đầu tiên chứa số nguyên dương $n$ $(1\le n\le {10}^5)$ là số lượng tam giác;
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ $(1\le a_i\le 30)$ với $a_i$ là màu của tam giác thứ $i$ $(1\le i\le n)$.

Dữ liệu luôn đảm bảo tổng tất cả các giá trị $n$ trong các bộ dữ liệu không vượt quá $5\times {10}^5$.

Dữ liệu ra

Trên $t$ dòng, dòng thứ $i$ in ra một số nguyên duy nhất là số tầng nhiều nhất của tòa tháp mà Tí xếp được của bộ dữ liệu thứ $i$ $(1\le i\le t)$.

Ràng buộc

• $1\le t\le 100$; $1\le n\le {10}^5$; tổng $n$ không vượt quá $5\times {10}^5$.
• $1\le a_i\le 30$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $n\le 200$.
• Subtask 2 ($30\%$ số điểm): $n\le {10}^5$, $a_i\le 20$.
• Subtask 3 ($50\%$ số điểm): Không có giới hạn gì thêm.

Ví dụ