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⁰ = “” (empty line)

aⁿ⁺¹ = a * aⁿ

   For a given string s print the largest n such that s = aⁿ 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 10⁵ characters.

Output

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

Samples