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

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

Палиндромная последовательность — это последовательность, которая равна перевернутой себе.

Задана последовательность из $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$. Любое целое значение встречается в $$$a$$$ не более двух раз.

Какова длина самой длинной палиндромной подпоследовательности последовательности $$$a$$$?

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

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

Затем следуют описания $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 250\,000$$$) — количество элементов последовательности.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

Любое целое значение встречается в $$$a$$$ не более двух раз. Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.

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

На каждый набор входных данных выведите одно целое число — длину самой длинной палиндромной подпоследовательности последовательности $$$a$$$.

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

Вот самые длинные палиндромные подпоследовательности для наборов входных данных из примера:

  • 2 1 3 1 5 2
  • 1 3 3 4 4 1 или 1 3 3 4 4 1
  • 1
  • 1 1
  • 4 4 2 5 7 2 3 или 4 4 2 5 7 2 3