La copia en tándem es una operación sobre ADN en la que se repite una secuencia de uno o más nucleótidos consecutivos y las repeticiones quedan directamente adyacentes. Es decir, se copia una secuencia consecutiva de nucleótidos y se pega justo después de la secuencia copiada. Por ejemplo, copiar $\mathrm{ATC}$ en $\mathrm{ATCG}$ produce $\mathrm{ATCATCG}$. Otra copia sobre el resultado puede producir $\mathrm{ATCATTCG}$. El siguiente ejemplo muestra una serie de copias desde $\mathrm{ATCG}$; en cada paso se copia la secuencia subrayada.

$$\underline{\mathrm{ATC}}\mathrm G\Rightarrow\mathrm{ATCA}\underline{\mathrm T}\mathrm{CG}\Rightarrow\underline{\mathrm{AT}}\mathrm{CATTCG}\Rightarrow\mathrm{ATATC}\underline{\mathrm{ATT}}\mathrm{CG}\Rightarrow\cdots$$

Decimos que $\mathrm{ATCG}$ produce todas estas secuencias mediante copias en tándem. Es fácil ver que puede producir secuencias diferentes eligiendo una parte diferente para copiar en cada paso. Además, en principio, $\mathrm{ATCG}$ puede producir infinitas secuencias continuando las copias tantas veces como sea necesario.

Normalmente, copiar una parte más larga es más costoso. Por ejemplo, $\underline{\mathrm{ATC}}\mathrm G\Rightarrow\mathrm{ATCATCG}$ copia tres nucleótidos y por tanto es más costoso que $\mathrm{ATCA}\underline{\mathrm T}\mathrm{CG}\Rightarrow\mathrm{ATCATTCG}$, que copia un solo nucleótido. En otras palabras, la longitud de la parte copiada en cada paso es crucial para determinar el coste.

Como es fácil copiar en tándem un único nucleótido, resulta práctico para el laboratorio ICPC almacenar secuencias en las que dos nucleótidos consecutivos siempre sean distintos; esto reduce el espacio de almacenamiento. Por ejemplo, $\mathrm{ATTTG}$ se obtiene copiando $\mathrm T$ dos veces desde $\mathrm{ATG}$, por lo que conviene almacenar solo la secuencia más corta $\mathrm{ATG}$ en lugar de $\mathrm{ATTTG}$.

Por un reciente recorte presupuestario, el laboratorio ICPC solo puede copiar en tándem como máximo dos nucleótidos de una vez; la parte copiada tiene longitud como máximo dos en cada paso. Sin embargo, puede repetir la operación tantas veces como quiera. Por ejemplo, dada $\mathrm{ABCD}$, copiar $\mathrm B$ produce $\mathrm{ABBCD}$ y copiar $\mathrm{BC}$ produce $\mathrm{ABCBCD}$. No se puede copiar la secuencia consecutiva $\mathrm{ABC}$ porque su longitud es mayor que dos.

Dadas una cadena origen $s$ y una cadena objetivo $t$, cuenta todas las subcadenas válidas $s\prime$ de $s$. Una subcadena es válida si, aplicando un número adecuado de copias en tándem a $s\prime$, se puede obtener una cadena $x$ que contenga $t$ como subcadena. No hay dos nucleótidos consecutivos iguales en la cadena origen, pero sí puede haberlos en la objetivo. Por ejemplo, $\mathrm{CCA}$ o $\mathrm{ATTGC}$ no pueden ser cadenas origen, pero sí cadenas objetivo.

Ahora, dadas $s=\mathrm{ACATGCAT}$ y $t=\mathrm{CCACATTT}$, tomamos la subcadena $s\prime=\mathrm{CATGC}$ de $s$ y realizamos esta serie de copias:

$$s\prime=\underline{\mathrm C}\mathrm{ATGC}\Rightarrow\mathrm C\underline{\mathrm{CA}}\mathrm{TGC}\Rightarrow\mathrm{CCACA}\underline{\mathrm T}\mathrm{GC}\Rightarrow\mathrm{CCACAT}\underline{\mathrm T}\mathrm{GC}\Rightarrow\mathrm{CCACATTTGC}$$

El resultado contiene $t$ como subcadena.

Este es otro ejemplo de subcadena. Para $s\prime=\mathrm{CAT}$:

$$s\prime=\underline{\mathrm{CA}}\mathrm T\Rightarrow\underline{\mathrm C}\mathrm{ACAT}\Rightarrow\mathrm{CCACA}\underline{\mathrm T}\Rightarrow\mathrm{CCACAT}\underline{\mathrm T}\Rightarrow\mathrm{CCACATTT}=t$$

Esto muestra que podemos producir la cadena objetivo desde $\mathrm{CAT}$ mediante una serie de copias en tándem.

Es fácil comprobar que el número total de subcadenas válidas de $s$ es $14$. Observa que el primer $\mathrm{CAT}$ y el segundo $\mathrm{CAT}$ de $s$ se cuentan como subcadenas válidas distintas. Por tanto, debes considerar todas las subcadenas de $s$ y contar cada una de las válidas individualmente.

Otro ejemplo: si $s=\mathrm{AB}$ y $t=\mathrm{BA}$, puedes tomar la subcadena $\mathrm{AB}$ y copiar $\mathrm{AB}$ en tándem. El resultado es $\mathrm{ABAB}$, que contiene $\mathrm{BA}$ como subcadena. Ninguna otra subcadena de $s$ puede producir $\mathrm{BA}$ como subcadena, así que el número de subcadenas válidas es uno.

Dadas una cadena origen $s$, sin caracteres consecutivos iguales, y una cadena objetivo $t$, escribe un programa que muestre el número de subcadenas válidas $s\prime$ de $s$. Una subcadena $s\prime$ es válida si una serie de copias en tándem puede producir una cadena que contenga $t$ como subcadena; en cada paso se pueden copiar como máximo dos caracteres consecutivos.

Entrada

Tu programa debe leer de la entrada estándar. La entrada consta de dos líneas: la primera es la cadena origen $s$ y la segunda la objetivo $t$. Cada cadena consta de letras mayúsculas de A a Z, y $1\le |s|,|t|\le 2\times 10^4$.

Salida

Tu programa debe escribir en la salida estándar. Imprime exactamente una línea con el número de subcadenas válidas en las que una serie de copias en tándem puede producir una cadena que contenga la cadena objetivo como subcadena.

A continuación se muestran la entrada y la salida de ejemplo para cuatro casos de prueba.

Ejemplos

Entrada 1

ACGCG
CCG

Salida 1

9

Entrada 2

TATCGC
TTCCG

Salida 2

6

Entrada 3

ABCABC
ABC

Salida 3

7

Entrada 4

ABCABC
ABCABC

Salida 4

1