Есть \(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\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите одно целое число \(k\): максимальное число команд, которые могут быть составлены при суммарном весе участников в команде, равном \(s\), если выбирать \(s\) оптимально.
Примечание
В первом наборе тестовых данных примера мы можем достичь оптимального ответа для \(s=6\). Тогда первая лодка будет использоваться участниками \(1\) и \(5\), а вторая лодка — участниками \(2\) и \(4\) (индексы совпадают с весами).
Во втором наборе тестовых данных примера мы можем достичь оптимального ответа для \(s=12\). Тогда первые \(6\) участников смогут образовать \(3\) пары.
В третьем наборе тестовых данных примера мы можем достичь оптимального ответа для \(s=3\). Ответ равен \(4\), потому что у нас есть \(4\) участника с весом \(1\) и \(4\) участника с весом \(2\).
В четвертом наборе тестовых данных примера мы можем достичь оптимального ответа для \(s=4\) или \(s=6\).
В пятом наборе тестовых данных примера мы можем достичь оптимального ответа для \(s=3\). Заметьте, что участник с весом \(3\) не может использовать лодку, потому что для него в списке нет подходящей пары.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|