Clean Up the Note

Little Z's class notes are in complete disarray. He only managed to record one example sentence and a list of forbidden letter pairs. The teacher stated that certain pairs of letters should never be adjacent (regardless of their order). For example, if the forbidden pair is ab, then both ab and ba are disallowed.

After returning home, Little Z noticed that his example sentence contains some of these forbidden adjacent pairs. In order to make the sentence legal, he can remove some of the letters (i.e. erase them). Your task is to determine the minimum number of letters that must be removed from the sentence so that no forbidden pair appears consecutively.

Formally, given a string s and a set of forbidden pairs, find the minimum number k such that there exists a subsequence of s (obtained by removing k characters) which does not contain any pair of consecutive letters (x, y) with
$$ (x,y)\in F, \quad\text{or equivalently} \quad (y,x)\in F. $$

inputFormat

The input consists of several lines:

• The first line contains a non-empty string s consisting of lowercase letters.
• The second line contains an integer n representing the number of forbidden pairs.
• Each of the following n lines contains exactly two distinct lowercase letters representing a forbidden pair. Note that if a pair ab is forbidden, then both ab and ba are not allowed as consecutive letters.

outputFormat

Output a single integer representing the minimum number of letters that need to be removed from s so that no forbidden pair appears as adjacent letters in the resulting sequence.

sample

ab
1
ab

1