EIU Programming Page for CIT

Năm nào cũng thế, cứ mùa Noel đến là Việt lại đau đầu với việc chuẩn bị quà cho các bạn nữ. Quyết không để mình rơi vào hoàn cảnh như những năm trước, Việt đã mua rất nhiều gấu bông, với đủ màu sắc khác nhau để làm quà. Theo Việt, một món quà là đạt yêu cầu nếu có một tấm thiệp “anh chỉ yêu mình em”, kèm theo 3 chú gấu bông có màu sắc đôi một khác nhau. Tất nhiên Việt muốn tìm cách chia gấu bông để số món quà đạt yêu cầu thu được là nhiều nhất, hãy giúp chàng trai khốn khổ của chúng ta, tính số món quà đạt yêu cầu lớn nhất mà anh ấy có thể thu được.

Input

Dòng 1: Số nguyên T, số test đề bài. (1≤T≤10).

T bộ test tiếp theo có dạng:

Dòng 1: Số nguyên N, số gấu bông đã mua. (1≤N≤500000)  .

Dòng 2: Gồm N số nguyên A₁…A_N là màu sắc của chú gấu bông thứ I (1≤A_i≤10¹⁸).

Output

Gồm T dòng tương ứng là kết quả ứng với T bộ test.

Example

Input:
1
4
1 3 2 5

Output:
1