Problems

# Power Strings

# 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:

**a**^{0} = “” (empty line)

**a ^{n}^{+1}** =

**a***

**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 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** = **a ^{n}** for some string

**a**.

Input example #1

abcd aaaa ababab

Output example #1

1 4 3