Longest Repeated Substring

Given a string S consisting of lowercase Latin letters, your task is to find the length of the longest substring that appears at least twice in S. The repeated substrings can overlap. For example, in the string "banana", the longest repeated substring is "ana", whose length is 3.

Note: If there is no repeated substring, output 0.

Constraints: The input string can be large, so an efficient algorithm (e.g. using suffix arrays and LCP computation) is required.

inputFormat

Input is read from standard input. The input consists of a single line that contains a non-empty string S of lowercase Latin letters.

outputFormat

Output to standard output a single integer representing the length of the longest repeated substring in S.## sample

banana

3