En streng $t$ med lengde $k$ bestående av små bokstaver kalles en CCPC-streng (Character-Character-Palindrome-Character) hvis og bare hvis følgende betingelser er oppfylt:

• $k \ge 4$;
• $t_1 = t_2 = t_k$;
• $t_3 t_4 \dots t_{k-1}$ er et palindrom.

En streng med lengde $m$ er et palindrom hvis og bare hvis det for alle $1 \le i \le m$ gjelder at det $i$-te tegnet i strengen er lik det $(m - i + 1)$-te tegnet i strengen.

For eksempel er ccpc, ppap, zzzz og aabcddcba CCPC-strenger, mens jinan, aaa og oovoo ikke er det.

En delstreng av en streng $s$ kan representeres av et par heltall $(l, r)$ som tilfredsstiller $1 \le l \le r \le |s|$, tilsvarende strengen $s_l s_{l+1} \dots s_r$. To delstrenger regnes som forskjellige hvis og bare hvis de valgte indeksparene $(l, r)$ ikke er like. Gitt en streng $s$ bestående av små bokstaver, beregn først antallet CCPC-delstrenger i $s$. Deretter utføres $n$ operasjoner, der hver operasjon setter inn en liten bokstav på venstre eller høyre side av $s$. Du må bestemme antallet CCPC-delstrenger i $s$ etter hver innsetting.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 100$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen en streng $s$ ($4 \le |s| \le 5 \times 10^5$) bestående av små bokstaver, som representerer startstrengen.

Den andre linjen inneholder et heltall $n$ ($1 \le n \le 5 \times 10^5$), som angir antallet operasjoner.

Den tredje linjen inneholder $n$ strenger med lengde $2$, $c_1, c_2, \dots, c_n$, adskilt med mellomrom, som representerer operasjonene i kronologisk rekkefølge. For hver streng $c_i$ er det første tegnet enten L eller R, som angir at innsettingen skjer på henholdsvis venstre eller høyre side av $s$, og det andre tegnet er en liten bokstav som angir tegnet som skal settes inn.

Det garanteres at verken summen av $|s|$ eller summen av $n$ over alle testtilfeller overstiger $5 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje som inneholder $n + 1$ heltall adskilt med mellomrom. Det første heltallet representerer svaret for startstrengen, og det $(i + 1)$-te heltallet ($1 \le i \le n$) representerer svaret etter de første $i$ operasjonene.

Eksempel

Inndata

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

Utdata

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

forklaring

For det andre testtilfellet blir $s$ etter alle operasjoner cccccpcpccppcppc. Dens CCPC-delstrenger inkluderer: $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}$.