E. Дружеские подарки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Арсений решил порадовать своих друзей — Дабира и Егора. Для этого он решил подарить каждому из них по массиву чисел одинаковой длины. Массив $$$b$$$ называется хорошим, если его элементы можно переставить так, что для всех $$$i \gt 1$$$ верно $$$b_i - b_{i - 1} = 1$$$.

Арсений хочет, чтобы Дабир и Егор могли играть с этими массивами. Для этого должны быть выполнены следующие условия:

  1. Каждый из подаренных массивов является хорошим.
  2. Если записать один массив за вторым(другими словами, сконкатенировать), полученный массив окажется хорошим.

У Арсения уже есть массив $$$a$$$ длины $$$n$$$. Он планирует вырезать оба массива из $$$a$$$, то есть выбрать в нём два непересекающихся отрезка одинаковой длины. Помогите Арсению определить максимальную возможную длину полученных массивов.

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

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

Далее следуют $$$t$$$ наборов входных данных.

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le n)$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$6000$$$.

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

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

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

В первом наборе входных данных невозможно выбрать $$$2$$$ массива, поэтому ответ $$$0$$$.

Во втором наборе входных данных максимальная длина выбранных массивов равна $$$1$$$. Можно выбрать массивы [$$$1$$$] и [$$$2$$$].

В четвертом наборе входных данных максимальная длина выбранных массивов равна $$$2$$$. Можно выбрать массивы [$$$2, 1$$$] и [$$$4, 3$$$].

В пятом наборе входных данных максимальная длина выбранных массивов равна $$$1$$$. Одним из способов выбрать массивы – [$$$1$$$] и [$$$2$$$]. Другими способами являются массивы [$$$2$$$] и [$$$3$$$], [$$$3$$$] и [$$$4$$$], или [$$$4$$$] и [$$$5$$$].