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