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

Вам дано целое число $$$n$$$ и массив целых чисел $$$a_1,a_2,\ldots,a_n$$$.

За одну операцию вы можете выбрать индекс $$$i$$$ ($$$1 \le i \lt n$$$), для которого $$$a_i \neq a_{i+1}$$$, и удалить оба элемента $$$a_i$$$ и $$$a_{i+1}$$$ из массива. После удаления $$$a_i$$$ и $$$a_{i+1}$$$ оставшиеся части массива соединяются.

Например, если $$$a=[1,4,3,3,6,2]$$$, то после применения операции с $$$i=2$$$ получившийся массив будет равен $$$[1,3,6,2]$$$.

Какова максимальная возможная длина массива из равных элементов, который можно получить из $$$a$$$ применением нескольких (возможно, нуля) операций, описанных выше?

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 5000$$$) — длина массива $$$a$$$.

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

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

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

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

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

Для первого набора входных данных оптимальной последовательностью операций будет: $$$[1,2,3,2,1,3,3] \rightarrow [3,2,1,3,3] \rightarrow [3,3,3]$$$.

Во втором наборе входных данных все элементы массива уже равны.

В третьем наборе входных данных единственной возможной последовательностью операций является: $$$[1,1,1,2,2,2] \rightarrow [1,1,2,2] \rightarrow [1,2] \rightarrow []$$$. Обратите внимание, что по условию два удаляемых элемента должны быть различны.

В четвёртом наборе входных данных оптимальной последовательностью является: $$$[1,1,2,2,3,3,1,1] \rightarrow [1,1,2,3,1,1] \rightarrow [1,1,1,1]$$$.

В пятом наборе входных данных единственным массивом из двух равных элементов, который можно получить, является $$$[4,4]$$$.