Dadas una cadena de caracteres ~s~ consistente solo de letras latinas minúsculas 'a', y una cadena de caracteres ~t~.

En un movimiento, puedes remplazar cualquier letra 'a' de la cadena ~s~ con la cadena ~t~ completa. Note que luego de remplazar la cadena ~s~, esta puede contener otras letras diferentes de 'a'.

Puedes realizar cualquier cantidad arbitraria de movimientos (incluso cero). ¿Cuántas cadenas diferentes se pueden obtener?

Dos cadenas son consideradas diferentes si tienen diferente tamaño, o difieren en algún índice.

Entrada

La primera línea de entrada contiene un solo entero ~q~ - el número de casos de prueba.

La primera línea de cada caso de prueba contiene una cadena ~s~ no vacía.

La segunda línea contiene una cadena ~t~ no vacía.

Salida

Por cada caso de prueba, imprima el número de cadenas diferentes ~s~ que pueden ser obtenidas luego de aplicar una cantidad arbitraria de movimientos (incluso cero).

Si el número es infinitamente largo, imprima -1. De otra forma imprímalo módulo ~10^9 + 7~.

Restricciones

~\bull~ En todos los casos de prueba se cumple que ~1 \leq q \leq 10^4~ y ~1\leq \vert s \vert , \vert t \vert \leq 10^3~.

Ejemplo de Entrada

3
aaaa
a
aa
abc
a
b

Ejemplo de Salida

1
-1
2

Explicación de los ejemplos

Caso de prueba 1:

Puedes remplazar cualquier letra 'a' con la cadena "a", pero eso no cambiará la cadena. Así que no importa cuantos movimientos se realicen, no se puede obtener más cadenas que la inicial.

Caso de prueba 2:

Puedes remplazar la segunda letra 'a' con la cadena "abc". La cadena ~s~ se convertirá en la cadena "aabc". Entonces, de puede volver a remplazar la segunda letra 'a', convirtiendo a la cadena ~s~ en "aabcbc". Este procedimiento se puede aplicar infinitas veces.

Caso de prueba 3:

Puedes o dejar la cadena ~s~ como está -realizando cero movimientos-, o remplazar la única letra de ~s~ con ~t~. La cadena ~s~ se convierte en "b", así que no se pueden realizar más movimientos en ella.