Böyüyən Sətirlər#3751
Gene və Gina özlərinə məxsus xüsusi bir fermaya sahibdirlər. Adi fermalardan fərqli olaraq, burada heyvanlar və tərəvəzlər deyil, sətirlər yetişdirilir. Sətir, simvolların ardıcıllığıdır və böyüdükcə yalnız sol və/və ya sağ tərəfdən simvollar əlavə edilir. Sətirlər heç vaxt simvolları itirmir və ya ortada yeni simvollar əlavə etmirlər.
Gene və Gina, sətirlərin böyümə mərhələlərində çəkilmiş fotoşəkillərdən ibarət bir kolleksiyaya sahibdirlər. Lakin, bu kolleksiya qeydə alınmadığı üçün hər bir fotoşəklin hansı sətirə aid olduğunu unudublar. Onlar sətirlərin böyümə prosesini təsvir edən bir divar hazırlamaq istəyirlər və bunun üçün uyğun fotoşəkil ardıcıllığını tapmaqda sizdən kömək istəyirlər.
Hər bir fotoşəkil bir sətiri təsvir edir. Fotoşəkillərin ardıcıllığı elə olmalıdır ki, əgər s_i ardıcıllıqda s_{i+1}-dən əvvəl gəlirsə, onda s_{i+1} s_i-dən böyümüş bir sətir ola bilər (yəni, s_i s_{i+1}-də ardıcıl alt sətir kimi görünməlidir). Həmçinin, təkrarlanan şəkillərdən istifadə etmək istəmirlər, buna görə də ardıcıllıqda bütün sətirlər fərqli olmalıdır.
Sizin vəzifəniz, verilmiş sətirlər dəstindən istifadə edərək, yuxarıdakı qaydalara uyğun hazırlana biləcək ən uzun ardıcıllığın ölçüsünü hesablamaqdır.
Hər bir test halı bir neçə sətirdən ibarətdir. İlk sətir, dəstdəki sətirlərin sayını göstərən N tam ədədini ehtiva edir (1 ≤ N ≤ 10^4). Sonrakı N sətirin hər biri İngilis əlifbasının kiçik hərflərindən ibarət fərqli, boş olmayan bir sətirdir. Hər bir test halında, bütün sətirlərin uzunluqlarının cəmi ən çox 10^6-dır.
Son test halı sıfır ehtiva edən bir sətirlə tamamlanır.
Hər bir test halı üçün hazırlana biləcək ən uzun fotoşəkil ardıcıllığının ölçüsünü təmsil edən bir tam ədədi bir sətirdə çıxış edin.
Nümunə 1