Let S be a string consisting of lowercase English letters. A nonempty string T is called a remarkable string of rank k with respect to S if the string k·T = T + T + ... + T (that is, T repeated k times) is a substring of S. More formally, S = U + k·T + V where U and V are some (possibly empty) strings.
Given a string S, find the maximum possible rank x such that there exists a string T which is a remarkable string of rank x with respect to S.
The only line of input contains the string S (1 ≤ |S| ≤ 10^6). It is guaranteed that S consists only of lowercase English letters.
Print one number: the maximum rank of a remarkable string with respect to S.