Цепочкой слов длины n назовем последовательность слов w1, w2, ..., wn такую, что для 1 ≤ i ≤ n слово wi является собственным префиксом слова wi + 1.
Напомним, что слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u.
Задано множество слов S = {s1, s2, ..., sm}. Найдите максимальную длину цепочки слов, которую можно построить, используя (возможно, не все) слова этого множества.
Входные данные
Первая строка входного файла содержит целое число m(1 ≤ m ≤ 255). Каждая из последующих m строк содержит по одному слову из множества S.
Все слова не пусты, имеют длину, не превосходящую 255 символов, и состоят только из строчных букв латинского алфавита.
Выходные данные
В выходной файл выведите ответ на задачу.
| Ввод |
Вывод |
|
3
a
ab
abc
|
3 |
|
5
a
ab
bc
bcd
add
|
2 |