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

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$. Вы можете выполнить следующую операцию:

  • Для всех индексов $$$i$$$ ($$$1 \leq i \leq n$$$) присвоить $$$a_i = |a_i - 2|$$$.

Найдите максимальное возможное количество вхождений любого целого числа в $$$a$$$ после выполнения операции произвольное число раз (возможно, ноль).

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

В первой строке каждого набора входных данных содержится целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных содержится целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Во второй строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число, обозначающее максимальное возможное количество вхождений любого целого числа в $$$a$$$ после выполнения операции произвольное число раз.

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

В первом наборе входных данных мы можем выполнить операцию один раз и получить $$$a = [|1 - 2|, |3 - 2|] = [1, 1]$$$, что означает, что максимальная возможная частота в $$$a$$$ равна $$$2$$$.

Во втором наборе входных данных максимальная частота некоторого целого числа в $$$a$$$ равна $$$3$$$. Можно показать, что, сколько бы операций мы ни выполнили, максимальная частота в $$$a$$$ никогда не превысит $$$3$$$.