A. Домашнее задание
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

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

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

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

Входные данные

В первой строке записана непустая строка s, состоящая из строчных латинских букв — исходное предложение на N-ском языке, написанное Сережей. Длина строки s не превосходит 105.

В следующей строке записано целое число k (0 ≤ k ≤ 13) — количество запрещенных пар букв.

В следующих k строках записаны описания запрещенных пар букв. В каждой строке находится ровно по две различные строчные латинские буквы без разделителей — запрещенные пары. Гарантируется, что каждая буква входит не более, чем в одну запрещенную пару.

Выходные данные

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

Примеры
Входные данные
ababa
1
ab
Выходные данные
2
Входные данные
codeforces
2
do
cs
Выходные данные
1
Примечание

В первом примере нужно удалить две буквы b.

Во втором примере нужно удалить вторую или третью букву. Второе ограничение никакой роли не играет.