Time Limit: 10 s
Memory Limit: 128 MB

Submission：12
AC：8
Score：99.49

An *edit step* is a transformation from one word *x* to another word *y* such that *x* and *y* are words in the dictionary, and *x* can be transformed to *y* by adding, deleting, or changing one letter. So the transformation from *dig* to *dog* or from *dog* to *do* are both edit steps. An *edit step ladder* is a lexicographically ordered sequence of words *w _{1}, w_{2}, ... w_{n}* such that the transformation from

For a given dictionary, you are to compute the length of the longest edit step ladder. The input to your program consists of the dictionary - a set of lower case words in lexicographic order - one per line. No word exceeds 16 letters and there are no more than 25000 words in the dictionary. The output consists of a single integer, the number of words in the longest edit step ladder.

input

cat
dig
dog
fig
fin
fine
fog
log
wine

output

5