팝송

밴드 The Length-First Searchers가 새 노래를 만들었다. 음악은 매혹적이고 가사는 귀에 잘 붙어서, 1위에 오를 가능성이 충분하다.

스튜디오에 가서 녹음하기 전에 남은 일은 음악과 가사를 합치는 것뿐이다. 노래는 인트로로 시작해 후렴이 이어지고 아웃트로로 끝난다고 이미 정했다 (요즘은 절을 좋아하는 사람이 없으니까). 노래의 각 부분에서는 가사의 일부를 부른다. 인트로와 아웃트로에서는 무엇을 불러도 되지만, 후렴에서는 더 질서 있게, 한 번에 가사 한 줄씩 불러야 한다. 음악의 박자와 맞추려면 후렴의 모든 줄의 길이가 같아야 한다. 인트로와 아웃트로에서 실제로 노래할 필요는 없지만, 후렴은 최소 두 줄로 이루어져야 한다.

가사의 어느 부분을 어느 파트에 넣을지 고르는 방법은 매우 많다. 그래서 아무렇게나 고르지 않고, 후렴의 라임 값을 최대로 만들기로 한다. 라임 값은 다음과 같이 정의한다. 후렴의 줄 수를 $N$, 모든 줄이 공유하는 가장 긴 공통 접미사의 길이를 $S$라고 하자. 이때 라임 값은 $N \cdot S$이다.

입력의 첫 번째이자 유일한 줄은 노래 가사인 문자열이다. 문자열은 소문자 알파벳 (a-z)과 밑줄 ("_")만으로 이루어진다. 길이는 $2$ 이상 $15000$ 이하이다.

달성할 수 있는 라임 값의 최댓값을 정수 하나로 출력한다.