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

문제

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

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

입력

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

출력

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

제한

힌트