Se te dan dos cadenas $a$ y $b$.

Una cadena $s$ es una subcadena de una cadena $t$ si $s$ se puede obtener de $t$ eliminando algunos caracteres (posiblemente ninguno) del principio y algunos caracteres (posiblemente ninguno) del final. En particular, la cadena vacía es una subcadena de cualquier cadena.

Se te dan $q$ cadenas de consulta. Para una cadena de consulta $c$ de longitud $m$ y para cada $k$ desde $1$ hasta $m$, cuenta las cadenas distintas $x$ tales que

• $x$ es una subcadena de $a$;
• $xc_1c_2\ldots c_k$ es una subcadena de $b$.

La cadena $x$ puede estar vacía. Dos cadenas $x$ se consideran iguales si son iguales como cadenas, independientemente de dónde aparezcan en $a$.

Entrada

La primera línea contiene un único entero $t$ ($1 \le t \le 10^4$): el número de casos de prueba.

La primera línea de cada caso de prueba contiene la cadena $a$ ($1 \le |a| \le 150\,000$).

La segunda línea contiene la cadena $b$ ($1 \le |b| \le 150\,000$).

La tercera línea contiene un único entero $q$ ($1 \le q \le 150\,000$): el número de consultas.

Cada una de las siguientes $q$ líneas contiene una cadena de consulta $c$ ($1 \le |c| \le 150\,000$).

Todas las cadenas están formadas por letras minúsculas del alfabeto inglés.

Se garantiza que la suma de $|a|$ sobre todos los casos de prueba no supera $150\,000$, que la suma de $|b|$ sobre todos los casos de prueba no supera $150\,000$ y que la suma de $|c|$ sobre todas las cadenas de consulta de todos los casos de prueba no supera $150\,000$.

Salida

Para cada consulta, imprime $|c|$ enteros: el $k$-ésimo de ellos debe ser el número de cadenas distintas $x$ que son subcadenas de $a$ y para las que $xc_1c_2\ldots c_k$ es una subcadena de $b$.

Ejemplos

Entrada 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

Salida 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

Entrada 2

1
ab
aaba
1
ab

Salida 2

4 2

Nota

En el segundo ejemplo, para el prefijo $a$, las cuatro cadenas válidas $x$ son la cadena vacía, $a$, $b$ y $ab$. En particular, tanto $a$ como $b$ deben contarse, aunque tengan la misma longitud. Para la cadena de consulta completa $ab$, solo son válidas la cadena vacía y $a$.