라임

아드리안은 라임을 좋아한다. 아드리안은 두 단어의 가장 긴 공통 접미사 길이가 더 긴 단어의 길이와 같거나 그보다 딱 1만큼 짧을 때, 그리고 그때만 두 단어가 라임을 이룬다고 본다. 즉, 단어 $A$와 $B$가 라임을 이루는 조건은 다음과 같다.

$\mathrm{LCS}(A, B) \ge \max(|A|, |B|) - 1$

여기서 $\mathrm{LCS}(A, B)$는 $A$와 $B$의 가장 긴 공통 접미사의 길이이고, $|A|$는 $A$의 길이이다.

어느 날 단편집을 읽던 아드리안은 이웃한 두 단어가 항상 라임을 이루도록 단어를 최대한 길게 늘어놓아 보기로 했다. 늘어놓는 단어는 주어진 단어 중에서 고르고, 같은 단어를 두 번 쓸 수 없다.

아드리안은 이 일에 싫증이 나서 다시 책을 읽으러 갔다. 대신 단어 $N$개가 주어질 때 이런 수열의 최대 길이를 구하는 프로그램을 작성하시오.

첫째 줄에 단어의 개수 $N$이 주어진다. ($1 \le N \le 500\,000$)

다음 $N$개 줄에 단어가 한 개씩 주어진다. 단어는 영어 소문자로만 이루어져 있고, 모두 서로 다르다. 단어 길이의 합은 $3\,000\,000$ 이하이다.

첫째 줄에 가장 긴 수열의 길이를 출력한다.