Typing на мобільному телефоні
Команда дослідників розробляє нову технологію для економії часу при наборі текстових повідомлень на мобільних пристроях. Вони працюють над новою моделлю, яка має повну клавіатуру, щоб користувачі могли вводити будь-яку окрему літеру, натискаючи відповідну клавішу. Таким чином, для введення слова довжиною P потрібно P натискань клавіш.
Однак це не достатньо швидко. Команда планує створити словник загальних слів, які користувач може вводити. Мета полягає в тому, щоб зменшити середню кількість натискань клавіш, необхідних для введення слів, які є в словнику. Під час набору слова, коли наступна літера визначена однозначно, система мобільного телефону введе її автоматично, без необхідності натискання клавіші. Поведінка системи мобільного телефону визначається наступними правилами:
Система ніколи не вгадує першу літеру слова, тому першу літеру завжди потрібно вводити вручну, натискаючи відповідну клавішу.
Якщо введено непорожню послідовність літер c_1c_2...c_n, і існує літера c така, що кожне слово в словнику, яке починається з c_1c_2...c_n, також починається з c_1c_2...c_nc, тоді система вводить c автоматично, без необхідності натискання клавіші. В іншому випадку система чекає на користувача.
Наприклад, якщо словник складається зі слів 'hello', 'hell', 'heaven' та 'goodbye', і користувач натискає 'h', система автоматично введе 'e', тому що кожне слово, яке починається з 'h', також починається з 'he'. Однак, оскільки є слова, що починаються з 'hel' і з 'hea', система тепер повинна чекати на користувача. Якщо користувач потім натискає 'l', отримуючи часткове слово 'hel', система автоматично введе другу 'l'. Коли введено 'hell', система не може вгадати, тому що можливо, що слово закінчилося, або можливо, що користувач хоче натиснути 'o', щоб отримати 'hello'. Таким чином, щоб ввести слово 'hello', користувачеві потрібно три натискання клавіш, 'hell' вимагає двох, а 'heaven' також вимагає двох, тому що коли поточний ввід 'hea', система може автоматично ввести залишок слова, повторно застосовуючи друге правило. Аналогічно, слово 'goodbye' потребує лише одного натискання клавіші, тому що після натискання початкової 'g' система автоматично заповнить усе слово. У цьому прикладі середня кількість натискань клавіш, необхідних для введення слова зі словника, становить (3 + 2 + 2 + 1)/4 = 2.00.
Ваше завдання — за даним словником обчислити середню кількість натискань клавіш, необхідних для введення слова зі словника з новою системою мобільного телефону.
Вхідні дані
Кожен тестовий випадок описується за допомогою кількох рядків. Перший рядок містить ціле число N, яке представляє кількість слів у словнику (1 ≤ N ≤ 10^5). Кожен з наступних N рядків містить непорожній рядок з не більше ніж 80 малих літер англійського алфавіту, що представляє слово у словнику.
У межах кожного тестового випадку всі слова різні, і сума довжин усіх слів не перевищує 10^6.
Вихідні дані
Для кожного тестового випадку виведіть рядок з раціональним числом, що представляє середню кількість натискань клавіш, необхідних для введення слова зі словника. Результат має бути виведений як раціональне число з точно двома цифрами після десяткової крапки, округлене за потреби.