英小文字 $n$ 個からなる文字列 $w$ が与えられます。$1 \le a \le b \le n$ を満たす位置、すなわち正整数 $a$ と $b$ に対して、部分文字列 $w_{a,b}$ を、文字列 $w$ の $a$ 番目の位置から $b$ 番目の位置までのすべての文字を順に取り出して得られる文字列として定義します。また、残りの文字列 $o_{a,b}$ を、文字列 $w$ から $a$ 番目の位置から $b$ 番目の位置までのすべての文字を削除して得られる文字列として定義します。

残りの文字列 $o_{a,b}$ にも $w_{a,b}$ が部分文字列として含まれるような、最も長い部分文字列 $w_{a,b}$ の長さを求めてください。

入力

最初の行には、英小文字からなる文字列 $w$ が与えられます。

出力

求める長さの最大値を出力してください。

小課題

$n$ を与えられた文字列の長さとします。

入出力例

入力 1

abcxyzabc

出力 1

3

入力 2

bbcdbcbbcbadadda

出力 2

5

注記

2 番目の例の説明： bbcdbcbbcbadadda → bbcdbcbadda