Una cadena $t$ de longitud $k$ formada por letras minúsculas se llama cadena CCPC (Character-Character-Palindrome-Character) si y solo si se cumplen las siguientes condiciones:

• $k \ge 4$;
• $t_1 = t_2 = t_k$;
• $t_3 t_4 \dots t_{k-1}$ es un palíndromo.

Una cadena de longitud $m$ es un palíndromo si y solo si para todo $1 \le i \le m$, el $i$-ésimo carácter de la cadena es igual al $(m - i + 1)$-ésimo carácter de la cadena.

Por ejemplo, ccpc, ppap, zzzz y aabcddcba son cadenas CCPC, mientras que jinan, aaa y oovoo no lo son.

Una subcadena de una cadena $s$ puede representarse mediante un par de enteros $(l, r)$ que satisfacen $1 \le l \le r \le |s|$, correspondiente a la cadena $s_l s_{l+1} \dots s_r$. Dos subcadenas se consideran diferentes si y solo si los pares de índices $(l, r)$ elegidos no son iguales. Dada una cadena $s$ formada por letras minúsculas, primero calcula el número de subcadenas CCPC en $s$. Luego se aplican $n$ operaciones, cada una insertando una letra minúscula en el lado izquierdo o derecho de $s$. Debes determinar el número de subcadenas CCPC en $s$ después de cada inserción.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 100$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene una cadena $s$ ($4 \le |s| \le 5 \times 10^5$) formada por letras minúsculas, que representa la cadena inicial.

La segunda línea contiene un entero $n$ ($1 \le n \le 5 \times 10^5$), que indica el número de operaciones.

La tercera línea contiene $n$ cadenas de longitud $2$, $c_1, c_2, \dots, c_n$, separadas por espacios, que representan las operaciones en orden cronológico. Para cada cadena $c_i$, el primer carácter es L o R, indicando que la inserción se realiza en el lado izquierdo o derecho de $s$, respectivamente, y el segundo carácter es una letra minúscula que indica el carácter a insertar.

Se garantiza que ni la suma de $|s|$ ni la suma de $n$ en todos los casos de prueba superan $5 \times 10^5$.

Salida

Para cada caso de prueba, imprime una sola línea con $n + 1$ enteros separados por espacios. El primer entero representa la respuesta para la cadena inicial, y el $(i + 1)$-ésimo entero ($1 \le i \le n$) representa la respuesta después de las primeras $i$ operaciones.

Ejemplo

Entrada

2
iloveccpc
6
Rj Ri Ln La Ln Ln
cpcpccp
9
Lc Lc Rp Rc Lc Lc Rp Rp Rc

Salida

1 1 1 1 1 1 2
0 2 3 3 4 5 7 8 8 9

Nota

Para el segundo caso de prueba, después de todas las operaciones, $s$ se convierte en cccccpcpccppcppc. Sus subcadenas CCPC incluyen: $s_{1\dots4} = \text{cccc}$, $s_{1\dots5} = \text{ccccc}$, $s_{2\dots5} = \text{cccc}$, $s_{3\dots10} = \text{cccpcpcc}$, $s_{4\dots7} = \text{ccpc}$, $s_{4\dots9} = \text{ccpcpc}$, $s_{9\dots13} = \text{ccppc}$, $s_{9\dots16} = \text{ccppcppc}$, $s_{11\dots14} = \text{ppcp}$.