【问题描述】

小 W 由于购物浪费了太多时间，导致他外语课都没有好好听。为什么是外语课？不是英语课？因为小 W 肯定会好好听英语课。由于没有好好听课， 小 W 的笔记全都记的杂乱无章，出现了好多错误的地方。 小 W 的笔记是如此的糟糕，以至于他只记了一句例句，而且自己还不知道是什么意思……然后在老师讲语法的时候， 小 W 又零星的记了几个字母对，老师说：这几个字母对是绝对不能相邻的，而且相邻是不关心字母的顺序的，比如老师说，‘ab’不能相邻，那么相同的，‘ba’也不能相邻。

现在小 W 到家了，打开了上课的笔记，然后他发现笔记有很多自相矛盾的地方：为什么下面的不能相邻的字母对会出现在上面的例句里面呢？纠结再三， 小 W 觉得下面的东西相对比较简单，所以记错的概率比较小……他决定在上面的例句里面擦掉几个字母，使得句子变得合法。

但是小 W 还要把礼物送给小 M，来不及整理笔记了，就把这个艰巨的任务留给了大家，请问大家， 小 W 最少要擦掉几个字母，才能使得上面的例句合法？

【输入格式】

第一行：一个整数 N。

第二行：一个长度为 N 的字符串，只包含小写字母，代表小 W 记下的例句。
第三行：一个整数 M，代表不能相邻的字母对的个数。

接下来 M 行：每行两个小写字母，代表不能相邻的字母对，因为小 W 太不认真了，所以可能有重复。

【输出格式】

一行一个整数：最少要擦除的字母数。

Sample 1

Input

4
jsoi
2
oi
mo

Output

1

Limitation

1s, 256MiB for each test case.
【数据规模】

对于 10% 的数据，M=0。
对于另外 30% 的数据，N≤1000。

对于 100% 的数据，N≤100000，M≤400。