Word Ladder

You have just started working for a puzzle company. They have a puzzle they call a Word Ladder. A solver starts from a given starting word and makes changes one letter at a time until reaching a target word, with no word in the chain appearing more than once. There are three ways to take a single step from one word to another:

• Change one letter
• Add one letter
• Remove one letter

So it is one step from COT to CAT, one step from CAT to SCAT, and one step from SCAT to SAT. Here is one word ladder from COT to SCAT:

COT ⇒ CAT ⇒ SAT ⇒ SCAT

Here is another word ladder from COT to SCAT:

COT ⇒ CAT ⇒ SCAT

The length of a word ladder is the number of words in it, so the examples above show a ladder of length 4 and a ladder of length 3. The second is the shortest possible ladder between COT and SCAT. Shorter ladders are considered better than longer ladders.

The company knows that, given two words, a smart solver will always find the best ladder — the shortest ladder — between them. To challenge their solvers, they are looking for long word ladders. Given a limited vocabulary, report the length of the longest word ladder a smart solver could find using only words from that vocabulary; that is, the longest of all best ladders.

The input consists of several datasets. Each dataset starts with an integer $N$ ($1 \le N \le 500$), the number of words in the vocabulary, followed by the words, one per line.

Each word consists of 1 to 50 lower-case letters only. There are no other characters and no white space.

The end of the input is indicated by a line containing a single zero.

For each dataset, print one line containing a single integer: the length of the longest ladder that a smart solver would find.