C. Лодочное соревнование
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ людей, желающих принять участие в лодочном соревновании. Вес $$$i$$$-го участника равен $$$w_i$$$. Принять участие могут только команды, состоящие из двух человек. Как организатор вы считаете честным допустить к соревнованию только команды с одинаковым суммарным весом.

Таким образом, для $$$k$$$ команд $$$(a_1, b_1)$$$, $$$(a_2, b_2)$$$, $$$\dots$$$, $$$(a_k, b_k)$$$, где $$$a_i$$$ — вес первого участника $$$i$$$-й команды, а $$$b_i$$$ — вес второго участника $$$i$$$-й команды, должно выполняться условие $$$a_1 + b_1 = a_2 + b_2 = \dots = a_k + b_k = s$$$, где $$$s$$$ — суммарный вес для каждой команды.

Ваша задача — выбрать такое число $$$s$$$, что количество команд, которые могут быть созданы, максимально возможное. Обратите внимание: каждый участник может состоять не более чем в одной команде.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

Входные данные

Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 50$$$) — количество участников. Вторая строка набора тестовых данных содержит $$$n$$$ целых чисел $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le n$$$), где $$$w_i$$$ — вес $$$i$$$-го участника.

Выходные данные

Для каждого набора тестовых данных выведите одно целое число $$$k$$$: максимальное число команд, которые могут быть составлены при суммарном весе участников в команде, равном $$$s$$$, если выбирать $$$s$$$ оптимально.

Пример
Входные данные
5
5
1 2 3 4 5
8
6 6 6 6 6 6 8 8
8
1 2 2 1 2 1 1 2
3
1 3 3
6
1 1 3 4 2 2
Выходные данные
2
3
4
1
2
Примечание

В первом наборе тестовых данных примера мы можем достичь оптимального ответа для $$$s=6$$$. Тогда первая лодка будет использоваться участниками $$$1$$$ и $$$5$$$, а вторая лодка — участниками $$$2$$$ и $$$4$$$ (индексы совпадают с весами).

Во втором наборе тестовых данных примера мы можем достичь оптимального ответа для $$$s=12$$$. Тогда первые $$$6$$$ участников смогут образовать $$$3$$$ пары.

В третьем наборе тестовых данных примера мы можем достичь оптимального ответа для $$$s=3$$$. Ответ равен $$$4$$$, потому что у нас есть $$$4$$$ участника с весом $$$1$$$ и $$$4$$$ участника с весом $$$2$$$.

В четвертом наборе тестовых данных примера мы можем достичь оптимального ответа для $$$s=4$$$ или $$$s=6$$$.

В пятом наборе тестовых данных примера мы можем достичь оптимального ответа для $$$s=3$$$. Заметьте, что участник с весом $$$3$$$ не может использовать лодку, потому что для него в списке нет подходящей пары.