Степінь рядка

Позначимо через $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$.

Приклади