두 문자열 $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$는 비어 있어도 된다. 두 문자열 $x$가 문자열로서 같다면, $a$의 어느 위치에 나타나는지와 관계없이 같은 문자열로 간주한다.

입력

첫 번째 줄에는 테스트 케이스의 개수인 정수 $t$ ($1\le t\le 10^4$)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 문자열 $a$ ($1\le |a|\le 150\,000$)가 주어진다.

두 번째 줄에는 문자열 $b$ ($1\le |b|\le 150\,000$)가 주어진다.

세 번째 줄에는 질의의 개수인 정수 $q$ ($1\le q\le 150\,000$)가 주어진다.

다음 $q$개의 줄에는 각각 하나의 질의 문자열 $c$ ($1\le |c|\le 150\,000$)가 주어진다.

모든 문자열은 영어 소문자로 이루어져 있다.

모든 테스트 케이스에 대한 $|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

참고

두 번째 예제에서 접두사 $a$에 대해 조건을 만족하는 네 문자열 $x$는 빈 문자열, $a$, $b$, $ab$이다. 특히 $a$와 $b$는 길이가 같더라도 둘 다 세어야 한다. 전체 질의 문자열 $ab$에 대해서는 빈 문자열과 $a$만 조건을 만족한다.