Masala #I9OZU6DMYV

Yosh qahramon Botir, bilimga chanqoq tadqiqotchi, uzoq yillar davomida turli o‘lkalarda bilim izlab yurdi. Nihoyat, u qadimiy bilimlarni o‘zida mujassam etgan mashhur kutubxonaga yetib keldi. Bu kutubxona avlodlardan-avlodlarga o‘tib kelayotgan murakkab jumboqlarni o‘z ichiga olardi.

Kutubxonadagi eng qimmatli bilimlardan foydalanish uchun, Botir bir ma’lumotlar tuzilmasi haqida bilimga ega bo‘lishi kerak edi. Bu tuzilma prefiks daraxti (yoki trie) deb ataladi.

Prefiks daraxti bu so‘zlar to‘plamidagi barcha prefikslarni quyidagicha ifodalaydigan ma’lumotlar tuzilmasidir:

• Daraxtning har bir qirrasida alifbodagi bir harf yozilgan bo‘ladi.
• Daraxtning ildizi bo‘sh prefiksni ifodalaydi.
• Daraxtning boshqa barcha tugunlari bo‘sh bo‘lmagan prefikslarni ifodalaydi. Tugunlar ildizdan ushbu tugungacha bo‘lgan qirralarda yozilgan harflarni birlashtirish orqali hosil qilingan prefikslarni ko‘rsatadi.
• Har bir tugundan chiqadigan qirralar orasida bir xil harf bo‘lmaydi (bu esa minimal tugunlar soni bilan daraxtni ifodalash imkonini beradi).

Prefiks daraxtiga namuna

Botir prefiks daraxtining qanday ishlashini tushunib olgach, haqiqiy jumboq boshlanadi!

Kutubxonachi, kichik ingliz harflaridan iborat bo‘lgan N ta so‘z ro‘yxatini taqdim etdi. Agar u oddiygina ushbu so‘zlar uchun prefiks daraxtidagi tugunlar sonini bilmoqchi bo‘lganida, jumboq juda oddiy bo‘lardi. Lekin u bundan qoniqmaydi. Kutubxonachi so‘zlarning har birini istalgan tartibda qayta joylashtirish orqali hosil bo‘lgan prefiks daraxtining eng kam tugunlar sonini bilishni istaydi.

Botirga jumboqni hal qilishda yordam bering va ushbu savolga javob toping!

Kirish faylining 1-satrida natural son \(N (1 \le N \le 16 \) kiritiladi.

Keyingi N satrning har birida 1 tadan so'z kiritiladi. So'z ingliz alifbosining kichik harflaridan tashkil topgan. 

Barcha so'zlarning umumiy uzunligi \( 10^6 \) dan oshmaydi.

Kutubxonachining jumbog'i javobini chop eting.