Александрик — известнейший разработчик программного обеспечения в сфере безопасности. Сегодня ему показалось, что его взломали, и он решил обновить пароли на всех своих аккаунтах.

Для этого Александрик придумал специальную трудновзламываемую строку $$$s$$$, которая почему-то состоит только из букв 'a' и 'b'. И теперь он хочет выбрать из нее наибольшую «отлично защищенную» подстроку, ибо только она обеспечит ему сохранность его драгоценных личных данных. Напомним, что подстрокой называется некоторый непрерывный подотрезок строки. Например, для строки ababaaa строка bab является подстрокой, так как она входит в эту строку непрерывно (ababaaa). В то же время, строка abb не является подстрокой, поскольку, хотя и входит в эту строку (ababaaa), не входит в эту строку непрерывно. Строка bbb также не является подстрокой, поскольку вообще не входит в эту строку.

Строка называется «отлично защищенной», если оказывается так, что каждый символ этой строки отличается от соответствующего символа в ее «перевернутой» версии (т. е. строки, в которой символы исходной строки записаны в обратном порядке). Так, например, строка abaabbab является «отлично защищенной», поскольку:

abaabbab

babbaaba

различаются в каждом символе. В то же время строка aaabaabb не является «отлично защищенной», т. к. ее «перевернутая» версия (bbaabaaa) совпадает с исходной строкой в третьей и шестой позиции.

Итак, помогите Александрику найти самую длинную подстроку его строки, которая является «отлично защищенной».

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