시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 32 13 8 40.000%

문제

상근이와 선영이는 조금 독특한 농장을 운영하고 있다. 보통 농장에서는 동물이나 야채를 기르지만, 그들은 문자열을 기른다.

문자열은 연속되는 문자를 나타낸다. 문자열을 자라면서 왼쪽이나 오른쪽에 문자가 추가된다. 문자가 없어지는 경우는 없고, 중간에 문자가 추가되는 경우도 없다.

상근이와 선영이는 문자열의 성장 과정을 사진으로 찍었다. 하지만, 사진에 따로 적어놓은 것이 없기 때문에, 어떤 사진이 어떤 문자열의 사진인지를 까먹었다. 그들은 사진을 벽에 그들이 자란 순서대로 전시해놓으려고 한다. 자 이제 사진의 순서를 찾는 프로그램을 작성해보자.

각 사진은 문자열로 나타낼 수 있다. 사진의 순서는 반드시 다음과 같은 규칙을 지켜야 한다. si가 si+1의 바로 앞에 오려면, si+1은 si가 자란 형태이어야 한다. 즉, si가 si+1의 연속된 부분 문자열이어야 한다. 상근이와 선영이는 같은 사진을 여러 번 찍지 않는다. 따라서, 사진의 순서에 포함되는 사진은 모두 다르다.

상근이와 선영이가 찍은 사진이 입력으로 주어진다. 이 때, 가장 긴 사진의 순서를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 사진의 개수 N이 주어진다. (1 ≤ N ≤ 104) 다음 N개 줄에는 사진에 찍혀있는 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 1000을 넘지 않는다.

각 테스트 케이스 마다 입력으로 주어지는 문자열의 길이의 합은 106을 넘지 않는다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 가장 긴 사진의 순서의 길이를 출력한다.

예제 입력

6
plant
ant
cant
decant
deca
an
2
supercalifragilisticexpialidocious
rag
0

예제 출력

4
2

힌트