Вам дана строка \(s\), состоящая из строчных латинских букв и/или знаков вопроса.
Тандемный повтор — это строка четной длины, такая, что ее первая половина равна второй половине.
Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Ваша цель — заменить каждый знак вопроса некоторой строчной латинской буквой таким образом, чтобы длина самой длинной подстроки, являющейся тандемным повтором, была максимально возможной.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальную длину самой длинной подстроки, являющейся тандемным повтором после замены каждого знака вопроса в строке некоторой строчной латинской буквой.
Если невозможно создать подстроки, являющиеся тандемными повторами в строке, выведите \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
zaabaabz
?????
code?????s
codeforces
|
6
4
10
0
|