[AHOI2005] 病毒检测

题目描述

科学家们在 Samuel 星球上的探险仍在继续。非常幸运的,在 Samuel 星球的南极附近,探险机器人发现了一个巨大的冰湖!机器人在这个冰湖中搜集到了许多 RNA 片段运回了实验基地。 科学家们经过几个昼夜的研究,发现这些 RNA 片段中有许多是未知的病毒! 每个 RNA 片段都是由 `A`、`C`、`T`、`G` 组成的序列。科学家们也总结出了 Samuel 星球上的“病毒模版片段”。一个模版片段是由 `A`、`C`、`T`、`G` 的序列加上通配符 `*` 和 `?` 来表示。其中 `*` 的意思是可以匹配上 $0$ 个或任意多个字符,而 `?` 的意思是匹配上任意一个字母。 如果一个 RNA 片段能够和“病毒模版片段”相匹配,那么这个 RNA 片段就是未知的病毒。 例如,假设 “病毒模版片段”为 `A*G?C`。RNA 片段:`AGTC`,`AGTGTC` 都是未知的病毒,而 RNA 片段 `AGTGC` 则不是病毒。 由于,机器人搜集的这些 RNA 片段中除去病毒的其他部分都具有非常高的研究价值。所以科学家们希望能够分辨出其中哪些 RNA 片段不是病毒,并将不是病毒的 RNA 片段运回宇宙空间站继续进行研究。 科学家将这项任务交给了小联。现在请你为小联编写程序统计哪些 RNA 片段不是病毒。

输入输出格式

输入格式


共 $N+2$ 行输入。 第一行有一个字符串,由 `A`、`C`、`T`、`G`、`*`、`?` 组成,表示“病毒模版片段”。“病毒模版片段”的长度不超过 $1000$。 第二行有一个整数 $N$,表示机器人搜集到的 RNA 片段的数目。 随后的 $N$ 行,每一行有一个字符串,由 `A`、`C`、`T`、`G` 组成,表示一个 RNA 片段。

输出格式


只有一行输出,为整数 $M$,即不是病毒的 RNA 片段的数目。

输入输出样例

输入样例 #1

A*G?C
3
AGTC
AGTGTC
AGTGC

输出样例 #1

1

说明

输入中的 RNA 片段 `AGTGC` 不是病毒。 对于所有数据,$0 < N < 500$。 特别的: - 每个 RNA 片段的长度不超过 $500$; - “病毒模版片段”和 RNA 片段的长度都至少为 $1$。