마술사

여러분은 Malnar 씨가 여가 시간에 마술을 한다는 이야기를 들었을지도 모릅니다. 그는 최근 유명한 TV 쇼 Penn & Teller: Fool Us에 출연해 전 세계를 놀라게 했습니다. 자신을 The Magical Mr. Malnar라고 소개하고 놀라운 멘탈리스트 마술을 선보여 모두의 마음을 사로잡았습니다.

그는 관객 가운데 열성적인 자원자를 불러내, 정확히 $N$개의 문자로 이루어진 임의의 문자열을 떠올려 달라고 부탁했습니다. 이후 관객을 즐겁게 하면서 가끔 자원자를 힐끗 보았고, 마지막에 "당신의 문자열에서 가장 긴 부분 회문의 길이는 $L$입니다"라고 선언했습니다. 자원자가 이것이 맞다고 확인하자 관객들은 깜짝 놀랐습니다.

그러나 예리한 시청자와 Malnar 씨의 가까운 지인들은 이것이 마음을 읽은 것이 아니라, 표정을 잘 읽는 능력과 맞물린 치밀하게 고른 말로 마술을 성공시키기에 충분한 정보를 흘린 것이라고 의심합니다.

Malnar 씨는 그저 장난을 치는 것처럼 보였지만, 때때로 $1 ≤ l ≤ r ≤ N$인 구간 $[l, r]$을 언급하며 자원자를 잠깐 바라보곤 했습니다. 소문에 따르면 그는 자원자의 표정만 보고도 $l$번째부터 $r$번째 글자까지(양 끝 포함)의 부분 문자열이 회문인지 판단할 수 있다고 합니다.

소문이 사실이라면, Malnar 씨가 자원자가 고른 비밀 문자열의 가장 긴 부분 회문을 알아낼 만큼 충분한 정보를 모았는지 확인하는 프로그램을 작성하세요.

1회문은 앞에서 읽으나 뒤에서 읽으나 같은 문자열입니다. 문자열의 부분 문자열은 어떤 $1 ≤ l ≤ r ≤ N$에 대해 그 문자열의 $l$번째부터 $r$번째 글자로 이루어진 문자열입니다. 부분 회문은 회문이기도 한 부분 문자열입니다.