Problem D
Power Strings

Given two strings $a$ and $b$ we define $a\cdot b$ to be their concatenation. For example, if $a = \text {"abc"}$ and $b = \text {"def"}$ then $a\cdot b = \text {"abcdef"}$. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: $a^0 = \text {""}$ (the empty string) and $a^{n+1} = a\cdot {a^ n}$.

Input

The input consists of up to $10$ test cases. Each test case is a line of input containing $s$, a string of lower case letters (a-z). The length of $s$ will be at least $1$ and will not exceed $2\, 000\, 000$ characters. A line containing a period follows the last test case.

Output

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

abcd
aaaa
ababab
.

1
4
3