Чудові підрядки

Нехай 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.

Приклади