Cuộc thi chèo thuyền

Có $n$ người muốn tham gia một cuộc thi chèo thuyền. Cân nặng của người thứ $i$ là $w_i$. Cuộc thi chỉ cho phép các đội gồm đúng hai người, và để đảm bảo công bằng, tất cả các đội tham gia phải có cùng tổng cân nặng.

Cụ thể, nếu có $k$ đội $(a_1,b_1),(a_2,b_2),\dots ,(a_k,b_k)$ (với $a_i$ và $b_i$ là cân nặng của hai người trong đội thứ $i$), thì điều kiện $a_1+b_1=a_2+b_2=\dots =a_k+b_k=s$ phải được thoả mãn, trong đó $s$ là tổng cân nặng chung của mỗi đội.

Hãy chọn $s$ sao cho số đội có thể tạo ra là lớn nhất có thể. Mỗi người chỉ được tham gia vào tối đa một đội. In ra số đội tối đa này.

Bạn phải trả lời $t$ bộ dữ liệu độc lập.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng thứ nhất chứa số nguyên $n$ — số người.
  • Dòng thứ hai chứa $n$ số nguyên $w_1,w_2,\dots ,w_n$ — cân nặng của các người.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên $k$ — số đội nhiều nhất có thể tạo ra khi chọn $s$ tối ưu.

Ràng buộc

• $1\le t\le 1000$
• $1\le n\le 50$
• $1\le w_i\le n$

Ví dụ