Злиття міст
Останні досягнення в інформаційних та комунікаційних технологіях дозволили надавати муніципальні послуги на більшій території швидше та з меншими витратами. Під впливом цього, а також для економії обмежених ресурсів, мери багатьох міст почали обговорювати можливість об'єднання своїх міст.
Звісно, існує багато перешкод для реалізації таких злиттів. Кожне місто має свою унікальну культуру, якою пишаються його мешканці. Однією з найбільших проблем є вибір назви для нового міста. Усі громадяни наполягають на тому, щоб нова назва містила хоча б частину оригінальної назви їхнього міста. Однак просте об'єднання всіх оригінальних назв зробило б назву занадто довгою для повсякденного використання.
Група мерів попросила вас розробити програму, яка знайде найкоротшу можливу назву для нового міста, що включає всі оригінальні назви об'єднаних міст. Якщо два або більше міст мають спільні частини, їх можна накласти. Наприклад, якщо міста "FUKUOKA", "OKAYAMA" та "YAMAGUCHI" мають бути об'єднані, "FUKUOKAYAMAGUCHI" є такою назвою, що включає всі три оригінальні назви міст. Хоча це включає всі символи назви міста "FUKUYAMA" в цьому порядку, вона не з'являється як послідовний рядок, і тому "FUKUYAMA" не вважається включеною в назву.
Вхідні дані
Вхідні дані складаються з кількох наборів. Кожен набір починається з рядка, що містить додатне ціле число n (n ≤ 14), яке вказує кількість міст, що мають бути об'єднані. Наступні n рядків містять назви міст великими літерами алфавіту, по одному в кожному рядку. Ви можете припустити, що жодна з оригінальних назв міст не перевищує 20 символів. Жодні два міста не мають однакової назви.
Кінець введення позначається рядком, що складається з нуля.
Вихідні дані
Для кожного набору даних виведіть довжину найкоротшої можливої назви нового міста в одному рядку.
Вихід не повинен містити жодних інших символів.