Se dan dos cadenas $s$ y $t$, ambas formadas por letras minúsculas.

Sea $s_{l,r}$ la subcadena de $s$ desde su $l$-ésimo carácter hasta su $r$-ésimo carácter con longitud $L = r - l + 1$. Decimos que $t$ aparece en el círculo de $s_{l,r}$ si y solo si existe una posición inicial $p$ ($0 \le p < L$) tal que para todo $0 \le k < |t|$, se cumple $s_{l,r}[(p + k) \bmod L] = t[k]$. Si $L < |t|$, entonces se considera que $t$ no aparece en el círculo de $s_{l,r}$.

Cuenta cuántos pares distintos $(l, r)$ satisfacen que $t$ aparece en el círculo de $s_{l,r}$.

Entrada

Cada archivo de prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $T$ ($1 \le T \le 2 \times 10^5$). A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene una cadena $s$ ($1 \le |s| \le 2 \times 10^5$).

La segunda línea contiene una cadena $t$ ($1 \le |t| \le 2 \times 10^5$).

Se garantiza que todas las cadenas consisten en letras minúsculas.

Para cada archivo de prueba, se garantiza que la suma de $|s|$ en todos los casos de prueba no supera $2 \times 10^5$, y la suma de $|t|$ en todos los casos de prueba no supera $2 \times 10^5$.

Salida

Para cada caso de prueba, imprime un entero en una sola línea, que representa el número de pares $(l, r)$ que satisfacen la condición.

Ejemplos

Entrada 1

3
cabcccabc
ccabcc
bcdabc
abcd
aaaxaaaxaaa
axaaaxaa

Salida 1

3
3
10

Entrada 2

4
aaaaaaaaa
a
abacab
caba
baaabaab
aabaaab
bbabbbabb
bbbabbb

Salida 2

45
4
2
3