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 $2000000$ 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