2 つの文字列 $a$ と $b$ が与えられます。

文字列 $t$ の先頭からいくつか（$0$ 個でもよい）の文字を削除し、末尾からいくつか（$0$ 個でもよい）の文字を削除することで文字列 $s$ が得られるとき、$s$ は $t$ の部分文字列であるといいます。特に、空文字列はすべての文字列の部分文字列です。

クエリとして $q$ 個の文字列が与えられます。長さ $m$ のクエリ文字列 $c$ に対して、$1$ から $m$ までの各 $k$ について、次の条件を満たす相異なる文字列 $x$ の個数を求めてください。

• $x$ は $a$ の部分文字列である。
• $xc_1c_2\ldots c_k$ は $b$ の部分文字列である。

文字列 $x$ は空でもかまいません。2 つの文字列 $x$ は、$a$ のどこに現れるかにかかわらず、文字列として等しければ同じものとみなします。

入力

最初の行には、テストケース数を表す整数 $t$（$1 \le t \le 10^4$）が 1 つ与えられます。

各テストケースの最初の行には、文字列 $a$（$1 \le |a| \le 150\,000$）が与えられます。

2 行目には、文字列 $b$（$1 \le |b| \le 150\,000$）が与えられます。

3 行目には、クエリ数を表す整数 $q$（$1 \le q \le 150\,000$）が 1 つ与えられます。

続く $q$ 行には、それぞれクエリ文字列 $c$（$1 \le |c| \le 150\,000$）が 1 つ与えられます。

すべての文字列は英小文字からなります。

すべてのテストケースにおける $|a|$ の総和は $150\,000$ 以下、すべてのテストケースにおける $|b|$ の総和は $150\,000$ 以下、すべてのテストケースのすべてのクエリ文字列における $|c|$ の総和は $150\,000$ 以下であることが保証されます。

出力

各クエリについて、$|c|$ 個の整数を出力してください。そのうち $k$ 番目の整数は、$a$ の部分文字列であり、かつ $xc_1c_2\ldots c_k$ が $b$ の部分文字列となるような、相異なる文字列 $x$ の個数としてください。

入出力例

入力 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

出力 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

入力 2

1
ab
aaba
1
ab

出力 2

4 2

注記

2 番目の入出力例では、接頭辞 a に対して条件を満たす 4 つの文字列 $x$ は、空文字列、a、b、ab です。特に、a と b は長さが同じであっても、両方を数える必要があります。クエリ文字列 ab 全体に対しては、空文字列と a だけが条件を満たします。