Power Strings

Given two strings $a$ and $b$ we define $a\ast b$ to be their concatenation.

For example, if $a="abc"$ and $b="def"$ then $a\ast b="abcdef"$.

If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way:

$a^0$ = “” (empty line)

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

For a given string $s$ print the largest $n$ such that $s=a^n$ for some string $a$.

Input

Each test case is a line representing $s$, a string of printable characters. The length of $s$ will be at least $1$ and will not exceed $10^6$ characters.

Output

For each input string $s$ print in a separate line the largest $n$ such that $s=a^n$ for some string $a$.

Examples