Зростаючі рядки
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.
Останній тестовий випадок завершується рядком, що містить нуль.
Вихідні дані
Для кожного тестового випадку виведіть один рядок з одним цілим числом, що представляє розмір найбільшої послідовності фотографій, яку можна створити.