영어 알파벳 소문자 $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

참고

두 번째 예제 설명: bbcdbcbbcbadadda → bbcdbcbadda