У Миши есть старенькая Nokia и много друзей. Так много, что Мише постоянно приходится тратить кучу времени на поиск нужного номера.

Имена друзей в телефонном справочнике упорядочены по алфавиту. От текущего имени в списке можно перейти к следующему с помощью кнопки «вниз», а к предыдущему — с помощью кнопки «вверх». Кроме того, список зациклен, то есть нажатие кнопки «вверх» для самого первого имени в справочнике переводит на последнее имя в нём, а нажатие кнопки «вниз» для последнего имени переводит на первое имя.

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

На одно нажатие кнопки у Миши уходит ровно одна секунда. Первая буква на кнопке набирается за одно нажатие, вторая за два и т.д. Клавиатура телефона выглядит так:

Дан список имён друзей Миши. Для каждого имени вычислите минимальное время, за которое Миша сможет выбрать это имя в списке.

В первой строке дано целое число n — количество записей в телефонном справочнике Миши (1 ≤ n ≤ 10⁵). Далее в n строках записано по одному непустому слову из строчных латинских букв. Слова перечислены в алфавитном порядке. Все записи в справочнике различны. Суммарная длина всех слов не превосходит 10⁵.

Выведите n чисел через пробел. i-е число должно равняться минимальному времени нахождения i-го имени в справочнике.