Little W is an algorithm contest participant who loves linguistics. In linguistics, phonetic substitution refers to replacing original words with words that have the same or similar pronunciation. Little W discovered that the process of phonetic substitution can be described using strings. Specifically, Little W defines phonetic substitution as the following string problem:

Given $n$ pairs of strings, the $i$-th ($1 \le i \le n$) pair is $(s_{i,1}, s_{i,2})$, satisfying $|s_{i,1}| = |s_{i,2}|$, where $|s|$ denotes the length of string $s$.

For a string $s$, the substitution of $s$ is defined as follows: * For a substring $y$ of $s$, if there exists $1 \le i \le n$ such that $y = s_{i,1}$, then $y$ is replaced by $y' = s_{i,2}$. Specifically, let $s = x + y + z$, where $x$ and $z$ can be empty, and "+" denotes string concatenation, then the substitution of $s$ results in the string $s' = x + y' + z$.

Little W poses $q$ questions. For the $j$-th ($1 \le j \le q$) question, two different strings $t_{j,1}$ and $t_{j,2}$ are given. She wants to know how many substitutions of $t_{j,1}$ can result in the string $t_{j,2}$. Two substitutions of $s$ are different if and only if the position of the substring $y$ is different or the pair $(s_{i,1}, s_{i,2})$ used for the substitution is different (i.e., $x, z$ are different or $i$ is different). You need to answer all the questions posed by Little W.

Input

The first line contains two positive integers $n$ and $q$, representing the number of string pairs and the number of questions posed by Little W, respectively.

The $i+1$-th line ($1 \le i \le n$) contains two strings $s_{i,1}$ and $s_{i,2}$, representing the $i$-th string pair.

The $j+n+1$-th line ($1 \le j \le q$) contains two strings $t_{j,1}$ and $t_{j,2}$, representing the $j$-th question posed by Little W.

Output

Output $q$ lines, where the $j$-th line ($1 \le j \le q$) contains a non-negative integer representing the number of substitutions of $t_{j,1}$ that result in the string $t_{j,2}$.

Examples

Input 1

1 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbb

Output 1

2
0

Note 1

For Little W's first query, there are 2 ways to substitute $t_{1,1}$ to obtain $t_{1,2}$: 1. Let $x, z$ be empty strings, $y = \text{xabcx}$, $i = 1$, then $y' = \text{xadex}$, resulting in $\text{xadex}$. 2. Let $x = \text{xa}$, $y = \text{bc}$, $z = \text{x}$, $i = 3$, then $y' = \text{de}$, resulting in $\text{xadex}$.

Input 2

3 4
a b
b c
c d
aa bb
aa b
a c
b a

Output 2

0
0
0
0

Examples 3

See the files replace/replace3.in and replace/replace3.ans in the contestant's directory. This example satisfies the constraints for test cases 11 and 12.

Examples 4

See the files replace/replace4.in and replace/replace4.ans in the contestant's directory. This example satisfies the constraints for test cases 15 and 16.

Constraints

Let $L_1 = \sum_{i=1}^n |s_{i,1}| + |s_{i,2}|$, $L_2 = \sum_{j=1}^q |t_{j,1}| + |t_{j,2}|$. For all test data, it is guaranteed that: $1 \le n, q \le 2 \times 10^5$; $2 \le L_1, L_2 \le 5 \times 10^6$; For all $1 \le i \le n$, $s_{i,1}, s_{i,2}$ consist only of lowercase English letters, and $|s_{i,1}| = |s_{i,2}|$; For all $1 \le j \le q$, $t_{j,1}, t_{j,2}$ consist only of lowercase English letters, and $t_{j,1} \neq t_{j,2}$.

Special Property A: $q = 1$.

Special Property B: A string $s$ is defined as "special" if and only if $s$ contains only characters 'a' and 'b', and the character 'b' appears exactly once in $s$. For all $1 \le i \le n$, $s_{i,1}, s_{i,2}$ are special, and for all $1 \le j \le q$, $t_{j,1}, t_{j,2}$ are special.