28895번 - Наскальная живопись 다국어

Доктор Брэйвстоун вместе с компанией нашел в Джуманджи древнюю пещеру. На стене этой пещеры была написана строка $s$, состоящая из строчных латинских букв. Теперь, чтобы продолжить прохождение, исследователям нужно определить максимальную длину палиндрома, который является подстрокой некоторого циклического сдвига строки $s$.

Палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево. Например, строки abacaba, abba и q --- являются палиндромами. Подстрокой строки называется некоторая последовательность подряд идущих символов этой строки. Циклическим сдвигом строки называется строка, полученная из исходной отрезанием некоторого префикса и дописыванием его в конец строки. Например, строки bacabaa, cabaaba и abacaba являются циклическими сдвигами строки abacaba.

В единственной строке дана непустая строка $s$, состоящая из строчных латинских букв, длина которой не превышает $10^6$.

Выведите единственное число --- искомую максимального длину палиндрома.