7 Maratona NexTI - 2018

Start

2018-05-25 17:00 UTC

7 Maratona NexTI - 2018

End

2018-05-28 17:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -365 days 5:51:54

Time elapsed

72:00:00

Time remaining

0:00:00

Problem F
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$.

Sample Input 1 Sample Output 1
abcd
aaaa
ababab
.
1
4
3