Category

Similar Problems

0731. Power Strings

Time limit : 1000 ms
Memory limit : 64 mb

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

Input contain a line representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 105 characters.

Output

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

Samples

Input

Output

1

abcd

1

2

aaaa

4

3

ababab

3

 

Tayyorladi: Azat Yusupov
Text from: e-olimp.com