You are given two strings $a$ and $b$.

String $s$ is a substring of string $t$ if $s$ can be obtained from $t$ by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end. In particular, the empty string is a substring of every string.

You are given $q$ query strings. For a query string $c$ of length $m$ and for every $k$ from $1$ to $m$, count the distinct strings $x$ such that

• $x$ is a substring of $a$;
• $xc_1c_2\ldots c_k$ is a substring of $b$.

The string $x$ may be empty. Two strings $x$ are considered the same if they are equal as strings, no matter where they occur in $a$.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$): the number of test cases.

The first line of each test case contains the string $a$ ($1 \le |a| \le 150\,000$).

The second line contains the string $b$ ($1 \le |b| \le 150\,000$).

The third line contains a single integer $q$ ($1 \le q \le 150\,000$): the number of queries.

Each of the next $q$ lines contains one query string $c$ ($1 \le |c| \le 150\,000$).

All strings consist of lowercase English letters.

It is guaranteed that the sum of $|a|$ over all test cases does not exceed $150\,000$, the sum of $|b|$ over all test cases does not exceed $150\,000$, and the sum of $|c|$ over all query strings of all test cases does not exceed $150\,000$.

Output

For each query, print $|c|$ integers: the $k$-th of them must be the number of distinct strings $x$ that are substrings of $a$ and for which $xc_1c_2\ldots c_k$ is a substring of $b$.

Examples

Input 1

4
ab
cababa
5
a
b
ab
ba
c
aaa
aaaaa
4
a
aa
aaa
aaaa
abc
xyz
4
a
xy
z
abc
banana
anaban
5
a
na
an
ban
n

Output 1

3
2
3 3
2 2
1
4
4 4
4 4 3
4 4 3 2
0
1 1
1
0 0 0
4
3 2
4 2
4 4 4
3

Input 2

1
ab
aaba
1
ab

Output 2

4 2

Note

In the second example, for the prefix a, the four valid strings $x$ are the empty string, a, b, and ab. In particular, a and b must both be counted even though they have the same length. For the full query string ab, only the empty string and a are valid.