Растущие строки
Gene и Джина владеют необычной фермой. Вместо того чтобы выращивать животных и овощи, как это делают на обычных фермах, они выращивают строки. Строка — это последовательность символов. Особенность их строк в том, что по мере роста они добавляют символы только слева и/или справа, никогда не теряя символов и не вставляя их в середину.
У Джины и Джина есть коллекция фотографий, запечатлевших строки на разных этапах их роста. Проблема в том, что коллекция не подписана, и они забыли, какая фотография относится к какой строке. Они хотят создать стену, чтобы показать процесс роста строк, но им нужна ваша помощь в нахождении правильной последовательности фотографий.
Каждая фотография изображает строку. Последовательность фотографий должна быть такой, что если s_i идет непосредственно перед s_{i+1} в последовательности, то s_{i+1} — это строка, которая могла вырасти из s_i (т.е. s_i является последовательной подстрокой в s_{i+1}). Кроме того, они не хотят использовать повторяющиеся фотографии, поэтому все строки в последовательности должны быть уникальными.
Дано множество строк, представляющих все доступные фотографии. Ваша задача — вычислить длину самой длинной последовательности, которую они могут создать, следуя указанным правилам.
Входные данные
Каждый тестовый случай задается несколькими строками. Первая строка содержит целое число N, обозначающее количество строк в наборе (1 ≤ N ≤ 10^4). Каждая из следующих N строк содержит уникальную непустую строку длиной не более 1000 строчных букв английского алфавита. В пределах каждого тестового случая сумма длин всех строк не превышает 10^6.
Последний тестовый случай завершается строкой, содержащей ноль.
Выходные данные
Для каждого тестового случая выведите одно целое число, представляющее длину самой длинной последовательности фотографий, которую можно создать.