Космический туризм в последние годы обрёл невиданную популярность. Желающих посмотреть вблизи на тройные звёзды, пройтись по поверхности небольшого астероида или погрузиться в глубину газового гиганта оказалось неожиданно много. Пассажирские корабли стали летать между всеми популярными звёздными секторами. Но есть небольшая проблема — перелёт до интересующего вас места может занимать до нескольких недель, и в это время надо как-то спасаться от дичайшей скуки, поскольку даже виды за иллюминатором редко радуют особым разнообразием. В связи с этим всё больше людей стало увлекаться чтением, а любители лунного языка — чтением визуальных новелл.

Визуальная новелла — это одно из переосмыслений обычной литературы, появившееся после массового переноса книг на электронные устройства. Основным отличием визуальной новеллы от обычной книги является то, что её сюжет, в отличие от обычной книги, может ветвиться, и читатель после некоторых страниц книги имеет более одного варианта выбора того, какая страница будет следующей. Такие моменты, когда читателю приходится делать выбор, называются ветвлениями.

Многие читатели любят исследовать новеллу целиком и полностью, прочитав все возможные варианты развития событий. После того как достигают одной из возможных концовок, они возвращаются в начало новеллы и могут попробовать другие пути развития сюжета. Вы, как автор новеллы «Песнь Аси», хотите упростить жизнь таким читателям. Во-первых, читатель после нескольких прочтённых до конца путей развития сюжета уже начинает забывать, для каких вариантов выбора он уже исследовал все возможные дальнейшие пути развития. Поэтому вы решили, что новелла не должна предлагать те варианты выбора, которые ведут в полностью исследованные читателем цепочки событий. Во-вторых, вы решили добавить кнопку, при нажатии которой новелла пропустит все промежуточные страницы до ближайшего ветвления или финала. Если же случайно нажать эту кнопку в тот момент, когда текущая страница является ветвлением, то ничего не произойдёт.

Вы уже составили все цепочки выборов, ведущие ко всем финалам, и хотите оценить, какое суммарное количество нажатий кнопок выбора развития и пропуска однозначных выборов потребуется читателю в лучшем случае, чтобы полностью прочитать всю новеллу во всех её вариантах развития сюжета.

В первой строке записано целое число n — количество различных концовок новеллы (1 ≤ n ≤ 10⁵). В i-й из следующих n строк записана непустая строка из строчных латинских букв, описывающая все сюжетные выборы на пути к i-й концовке. Гарантируется, что ни одна из строк не является префиксом другой строки. Суммарная длина строк не превосходит 10⁵.

Выведите минимальное количество нажатий на кнопки, необходимое для того, чтобы прочитать все возможные варианты развития сюжета новеллы.

Если обозначить нажатия кнопки выбора латинскими буквами, а нажатия кнопки пропуска однозначных выборов — символом «*», одна из оптимальных стратегий в приведённом примере имеет вид «b*c*».