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.

Input

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

Output

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)~.

Scoring

Sample Input 1

4
5
1 4 3 2 1
15
8 8 8 5 7 3 4 2 3 4 3 3 5 6 1
3
2 2 2
3
2 1 2

Sample Output 1

0
3
1
1

Notes

Với bộ dữ liệu thứ ~2~, Tí chọn dãy liên tiếp ~[3, 4, 2, 3, 4, 3, 3]~ và xếp thành tòa tháp ~3~ tầng.