B. String
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two strings $$$S_1$$$ and $$$S_2$$$ of equal length (indexed from $$$1$$$).

Now you need to answer $$$q$$$ queries, with each query consists of a string $$$T$$$.

The query asks how many triplets of integers $$$(i, j, k)\ (1\le i \le j \lt k\le |S_1|)$$$ satisfy the condition $$$S_1[i,j]+S_2[j+1,k]=T$$$.

Here $$$S[l,r]$$$ denotes the substring of $$$S$$$ with index form $$$l$$$ to $$$r$$$, and "+" denotes concatenation of strings.

Input

The first line contains a string $$$S_1$$$ .

The second line contains a string $$$S_2$$$ .

It is guaranteed that $$$1\le|S_1|=|S_2|\le 10^5$$$.

The third line contains a positive integer $$$q\ (1\leq q\leq 2\times 10^5)$$$, representing the number of queries.

The next $$$q$$$ lines each contain a string $$$T\ (1\leq |T|\leq 2\times 10^5)$$$, representing the query strings.

It is guaranteed that $$$\sum|T|\leq 2\times 10^5$$$ and all the strings input only consisting of lowercase letters.

Output

For each query, output a line with a positive integer representing the number of triplets that satisfy the condition.

Example
Input
aaababaa
aababbca
7
aa
abb
aab
ab
abc
bb
ba
Output
3
1
3
2
2
1
0