Problem Statement

You are given a string S. Takahashi may perform the following operation 0 or more times:

• Choose an integer i such that $1 \leq i \leq |S|$ and change the i-th character of S to *.

Takahashi's objective is to make S not contain any of $N strings T_1,T_2,\ldots,T_N$ as a substring.
Find the minimum number of operations required to achieve the objective.

Input

Input is given from Standard Input in the following format:
S
N
T_1
T_2
$\vdots$
T_N

Output

Print the answer.

Constraints

• $1 \leq |S| \leq 5 \times 10^5$
• $1 \leq N$
• N is an integer.
• $1 \leq |T_i|$
• $\sum{|T_i|} \leq 5 \times 10^5$
• $T_i \neq T_j$ if $i \neq j$.
• S and T_i are strings consisting of lowercase English letters.

Sample Input 1

abcdefghijklmn
3
abcd
ijk
ghi

Sample Output 1

2

If he performs the operation twice by choosing 1 and 9 for i, S becomes bcdefghjklmn; now it does not contain abcd, ijk, or ghi as a substring.

Sample Input 2

atcoderbeginnercontest
1
abc

Sample Output 2

0

No operation is needed.

Sample Input 3

aaaaaaaaa
2
aa
xyz

Sample Output 3

4

见题面 Input 部分

见题面 Output 部分