Сережа посещает кружок, на котором изучает N-ский язык. На каждом занятии ему дают домашнее задание. На этот раз ему задали перевести некоторое предложение на N-ский язык. Предложения в N-ском языке представляют собой строки, состоящие из строчных латинских букв без пробелов и знаков препинания.

Сережа вспомнил про задание за полчаса до следующего занятия и быстро что-то написал. Но потом он вспомнил, что на прошлом занятии ему рассказывали про грамматику N-ского языка. Согласно правилам, в N-ском языке есть некоторые «запрещенные» пары букв, которые никогда не могут стоять рядом в предложении, причем порядок букв не имеет значения (например, если запрещена пара букв «ab», то запрещены любые вхождения подстрок «ab» и «ba»). Кроме того, буквы в каждой паре различны, и каждая буква участвует не более, чем в одной запрещенной паре.

Теперь Сережа хочет исправить свое предложение, чтобы в нем не было «запрещенных» пар букв, стоящих рядом. Но времени осталось мало, и он решил просто вычеркнуть некоторые буквы из предложения. Какое минимальное количество букв ему придется вычеркнуть? При вычеркивании буквы она «удаляется», то есть буквы, находящиеся слева и справа от нее (если такие были), становятся соседними. Например, если вычеркнуть из строки «aba» первую букву получится строка «ba», а если вычеркнуть вторую получится «aa».