Пусть \textbf{S }- строка, состоящая из прописных букв английского алфавита. Непустая строка \textbf{T }называется \textit{замечательной} ранга \textbf{k }по отношению к \textbf{S}, если строка \textbf{k·T} = \textbf{T} + \textbf{T} + ... + \textbf{T} (строка \textbf{T }повторяется \textbf{k }раз) является подстрокой \textbf{S}. Более формально \textbf{S} = \textbf{U} + \textbf{k·T} + \textbf{V}, где \textbf{U }и \textbf{V }некоторые (возможно пустые) строки. Задана строка \textbf{S}. Найдите наибольший возможный ранг \textbf{x }такой, что существует строка \textbf{T}, являющаяся замечательной строкой ранга \textbf{x }по отношению к \textbf{S}. \InputFile Строка \textbf{S }(\textbf{1 }≤ \textbf{|S| }≤ \textbf{10^6}), состоящая только из прописных букв английского алфавита. \OutputFile Вывести одно число: максимальный ранг замечательной строки по отношению к \textbf{S}.