Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

Вам дана строка $$$s$$$, состоящая из строчных латинских букв и/или знаков вопроса.

Тандемный повтор — это строка четной длины, такая, что ее первая половина равна второй половине.

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

Ваша цель — заменить каждый знак вопроса некоторой строчной латинской буквой таким образом, чтобы длина самой длинной подстроки, являющейся тандемным повтором, была максимально возможной.

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

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

В единственной строке каждого набора входных данных записана строка $$$s$$$ ($$$1 \le |s| \le 5000$$$), состоящая только из строчных латинских букв и/или знаков вопроса.

Общая длина строк во всех наборах входных данных не превосходит $$$5000$$$.

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

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

Если невозможно создать подстроки, являющиеся тандемными повторами в строке, выведите $$$0$$$.

Пример
Входные данные
4
zaabaabz
?????
code?????s
codeforces
Выходные данные
6
4
10
0