단어 사다리

당신은 어느 퍼즐 회사에서 일하게 되었습니다. 이 회사에는 단어 사다리(Word Ladder)라고 부르는 퍼즐이 있습니다. 푸는 사람은 주어진 시작 단어에서 출발해 한 번에 한 글자씩 바꾸어 목표 단어에 도달하며, 이때 사슬(chain)에 등장하는 어떤 단어도 두 번 이상 나타나서는 안 됩니다. 한 단어에서 다른 단어로 한 걸음 이동하는 방법은 다음 세 가지입니다.

• 한 글자를 바꾼다
• 한 글자를 추가한다
• 한 글자를 제거한다

예를 들어 COT에서 CAT으로 가는 것은 한 걸음이고, CAT에서 SCAT으로 가는 것도 한 걸음, SCAT에서 SAT으로 가는 것도 한 걸음입니다. 다음은 COT에서 SCAT으로 가는 하나의 단어 사다리입니다.

COT ⇒ CAT ⇒ SAT ⇒ SCAT

다음은 COT에서 SCAT으로 가는 또 다른 단어 사다리입니다.

COT ⇒ CAT ⇒ SCAT

단어 사다리의 길이는 그 안에 들어 있는 단어의 개수입니다. 따라서 위의 두 예는 각각 길이 4인 사다리와 길이 3인 사다리를 보여 줍니다. 두 번째 사다리는 COT과 SCAT 사이에서 가능한 가장 짧은 사다리입니다. 더 짧은 사다리가 더 긴 사다리보다 좋은 것으로 여겨집니다.

이 회사는 두 단어가 주어지면 똑똑한 풀이자가 항상 그 둘 사이의 가장 좋은(즉, 가장 짧은) 사다리를 찾아낸다는 것을 알고 있습니다. 풀이자에게 도전 과제를 주기 위해, 회사는 긴 단어 사다리를 찾고 있습니다. 제한된 어휘가 주어졌을 때, 그 어휘에 속한 단어만 사용하여 똑똑한 풀이자가 찾아낼 수 있는 가장 긴 단어 사다리의 길이, 즉 모든 가장 좋은 사다리들 가운데 가장 긴 것의 길이를 구하세요.

입력은 여러 개의 데이터 집합으로 이루어집니다. 각 데이터 집합은 어휘에 들어 있는 단어의 수를 나타내는 정수 $N$ ($1 \le N \le 500$)으로 시작하고, 그다음 줄부터 단어가 한 줄에 하나씩 주어집니다.

각 단어는 1글자 이상 50글자 이하의 소문자 알파벳으로만 이루어집니다. 그 밖의 다른 문자나 공백은 없습니다.

입력의 끝은 0 하나만 있는 줄로 표시됩니다.

각 데이터 집합에 대해, 똑똑한 풀이자가 찾아낼 수 있는 가장 긴 사다리의 길이를 나타내는 정수 하나를 한 줄에 출력하세요.