Problems

# Power Strings

Given two strings a and b we define a*b to be their concatenation.

For example, if a = "abc" and b = "def" then a*b = "abcdef".

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

a0 = “” (empty line)

an+1 = a * an

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

Input

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

Output

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

Time limit 1 second
Memory limit 64 MiB
Input example #1
abcd
aaaa
ababab

Output example #1
1
4
3