Блок строки

Блоком строки T в позиции i называется самая длинная подстрока в T, начинающаяся с позиции i и совпадающая с префиксом этой строки. Длина блока в позиции 0 равна нулю. Требуется определить длину наибольшего блока в данной строке T.

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

Входной стандартный поток содержит одну строку T (1 ≤ size(T) ≤ 10^5), состоящую исключительно из букв латинского алфавита.

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

Выведите одно число — длину наибольшего блока.

Примеры