Замечательные подстроки

Пусть S - строка, состоящая из прописных букв английского алфавита. Непустая строка T называется замечательной ранга k по отношению к S, если строка k·T = T + T + ... + T (строка T повторяется k раз) является подстрокой S. Более формально S = U + k·T + V, где U и V некоторые (возможно пустые) строки.

Задана строка S. Найдите наибольший возможный ранг x такой, что существует строка T, являющаяся замечательной строкой ранга x по отношению к S.

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

Строка S (1 ≤ |S| ≤ 10^6), состоящая только из прописных букв английского алфавита.

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

Вывести одно число: максимальный ранг замечательной строки по отношению к S.

Примеры