JYY has recently obtained an arcane book from a friend and is now studying the JSOI magic within it.

JSOI magic acts on strings consisting only of lowercase letters. The foundation of JSOI magic is the magic transformation. There are $N$ transformation rules, where each rule is a triple $(a, b, c)$. Each of $a, b, c$ represents a character. It is guaranteed that $c$ is either empty or lexicographically greater than both $a$ and $b$, and for any given pair $(a, b)$, there is at most one corresponding transformation rule.

If a string $t$ undergoes one step of magic transformation, we find the leftmost position $i$ such that the two characters at positions $i$ and $i+1$ match the $a$ and $b$ of some transformation rule, and replace these two characters with the $c$ from that rule. If $c$ is empty, the two characters are deleted.

The arcane book can be viewed as a string $S$ consisting only of lowercase letters. Through his studies, JYY has learned that a substring $T$ of $S$ is a "magic substring" if it can be transformed into an empty string through a finite number of magic transformations.

Now, JYY wants to know how many substrings of $S$ are magic substrings. Note that substrings at different positions are considered distinct.

Input

The first line contains a string $s$. The second line contains a positive integer $N$, the number of transformation rules. The next $N$ lines each contain three space-separated characters $a_i, b_i, c_i$, representing a transformation rule. If $c_i$ is empty, it is represented by an asterisk "*".

Output

Output a single integer representing the number of magic substrings.

Constraints

• For 20% of the data, $|S| \le 100$.
• For another 20% of the data, all transformation rules result in an empty string.
• For 100% of the data, $0 \le N \le 50$, $1 \le |S| \le 200000$.

Examples

Input 1

abccc
2
a b c
c c *

Output 1

4