SMS-сообщение представляет собой строку, содержащую прописные и строчные латинские буквы, цифры, пробел, точку, запятую и знак «плюс». Для набора сообщения на старых кнопочных мобильных телефонах используются клавиши с цифрами и клавиша « # ». За цифровыми клавишами закреплены символы, которые можно ввести в сообщении:

Кроме того, однократное нажатие клавиши «*» позволяет переключаться между вводом прописных и строчных букв.

Для того, чтобы набрать символ из сообщения, необходимо нажать соответствующую клавишу столько раз, каким по порядку находится нужный символ в списке символов, закреплённых за клавишей. Так, для набора буквы R потребуется нажать клавишу «7» три раза, для набора цифры 9 соответствующую клавишу необходимо нажать пять раз.

Для того, чтобы последовательно набирать символы, закреплённые за одной клавишей и записанные в одном регистре (прописные либо строчные), необходимо после ввода предыдущего символа выдержать паузу, и только потом начинать ввод следующего символа. Так для ввода строки NO необходимо дважды нажать клавишу «6», выдержать паузу, а затем трижды нажать эту же клавишу.

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

Input

Первая строка файла содержит число 1 или 2 — признак того, какой режим ввода букв включён изначально (1 — прописные, 2 — строчные). Во второй строке записан текст сообщения — непустая строка длиной не более 30000 символов (в 50 % тестов длина строки не превосходит 255 символов). Кроме того, в 20 % тестов текст сообщения содержит только латинские буквы, записанные в одном регистре.

Output

Целое положительное число — время, затраченное на набор сообщения.

Examples

input.txt	output.txt
1 HELLO	22
2 My phone is +375286198121	127
2 MaMa	22