Степень строки

Обозначим через $a\ast b$ конкатенацию строк $a$ и $b$.

Например, если $a="abc"$ и $b="def"$ то $a\ast b="abcdef"$.

Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:

$a^0$ = “” (пустая строка)

$a^{n+1}=a\ast a^n$

По заданной строке $s$ необходимо найти наибольшее значение $n$, для которого $s=a^n$ для некоторой строки $a$.

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

Каждый тест состоит из одной строки $s$, содержащей печатные (отображаемые) символы. Строка $s$ содержит не менее одного и не более $10^6$ символов.

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

Для каждой входной строки $s$ вывести в отдельной строке наибольшее значение $n$, для которого $s=a^n$ для некоторой строки $a$.

Примеры