CF154A.Hometask

Sergey attends lessons of the N-ish language. Each lesson he receives a hometask. This time the task is to translate some sentence to the N-ish language. Sentences of the N-ish language can be represented as strings consisting of lowercase Latin letters without spaces or punctuation marks.

Sergey totally forgot about the task until half an hour before the next lesson and hastily scribbled something down. But then he recollected that in the last lesson he learned the grammar of N-ish. The spelling rules state that N-ish contains some "forbidden" pairs of letters: such letters can never occur in a sentence next to each other. Also, the order of the letters doesn't matter (for example, if the pair of letters "ab" is forbidden, then any occurrences of substrings "ab" and "ba" are also forbidden). Also, each pair has different letters and each letter occurs in no more than one forbidden pair.

Now Sergey wants to correct his sentence so that it doesn't contain any "forbidden" pairs of letters that stand next to each other. However, he is running out of time, so he decided to simply cross out some letters from the sentence. What smallest number of letters will he have to cross out? When a letter is crossed out, it is "removed" so that the letters to its left and right (if they existed), become neighboring. For example, if we cross out the first letter from the string "aba", we get the string "ba", and if we cross out the second letter, we get "aa".

谢尔盖正在学习“N语”课程。每次课后，他都会收到一项家庭作业。这次的任务是将某个句子翻译成“N语”。N语的句子可表示为仅由小写拉丁字母组成的字符串，中间不含空格或标点符号。

谢尔盖直到下节课开始前半小时才想起这项作业，于是匆忙胡乱写下了些内容。但随后他回忆起上一节课刚学过N语的语法规则：N语中存在若干“禁用”字母对——即这些字母绝不能在句子中相邻出现。此外，字母的顺序无关紧要（例如，若字母对“ab”被禁用，则子串“ab”和“ba”的出现均被禁止）。同时，每个禁用字母对中的两个字母互不相同，且每个字母至多出现在一个禁用字母对中。

现在，谢尔盖希望修改自己写的句子，使其不包含任何相邻的“禁用”字母对。但他时间紧迫，因此决定仅通过划掉（即删除）句中某些字母来实现修正。他最少需要划掉多少个字母？当某个字母被划掉后，其左右两侧的字母（如果存在）将变为相邻。例如，若从字符串 "aba" 中划掉第一个字母，得到字符串 "ba"；若划掉第二个字母，则得到 "aa"。

The first line contains a non-empty string s, consisting of lowercase Latin letters — that's the initial sentence in N-ish, written by Sergey. The length of string s doesn't exceed 105.

The next line contains integer k (0 ≤ k ≤ 13) — the number of forbidden pairs of letters.

Next k lines contain descriptions of forbidden pairs of letters. Each line contains exactly two different lowercase Latin letters without separators that represent the forbidden pairs. It is guaranteed that each letter is included in no more than one pair.

第一行包含一个非空字符串 $s$，由小写拉丁字母组成——这是谢尔盖所写的初始的“N 语”句子。字符串 $s$ 的长度不超过 $10^5$。

第二行包含一个整数 $k$（$0 \leq k \leq 13$）——禁止的字母对数量。

接下来的 $k$ 行描述了被禁止的字母对。每行恰好包含两个不同的小写拉丁字母，中间无分隔符，表示一个被禁止的字母对。保证每个字母至多出现在一个禁止对中。

Print the single number — the smallest number of letters that need to be removed to get a string without any forbidden pairs of neighboring letters. Please note that the answer always exists as it is always possible to remove all letters.

输出一个数字——即需要删除的最少字母数量，使得剩余字符串中不包含任何禁止的相邻字母对。请注意，答案一定存在，因为总是可以删除所有字母。

In the first sample you should remove two letters b.

In the second sample you should remove the second or the third letter. The second restriction doesn't influence the solution.

在第一个样例中，你应该移除两个字母 b。

在第二个样例中，你应该移除第二个或第三个字母。第二个限制条件不影响该解。