En sträng $t$ av längd $k$ bestående av små bokstäver kallas en CCPC-sträng (Character-Character-Palindrome-Character) om och endast om följande villkor är uppfyllda:

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

En sträng av längd $m$ är ett palindrom om och endast om det för alla $1 \le i \le m$ gäller att det $i$-te tecknet i strängen är lika med det $(m - i + 1)$-te tecknet i strängen.

Till exempel är ccpc, ppap, zzzz och aabcddcba CCPC-strängar, medan jinan, aaa och oovoo inte är det.

En delsträng av en sträng $s$ kan representeras av ett par heltal $(l, r)$ som uppfyller $1 \le l \le r \le |s|$, vilket motsvarar strängen $s_l s_{l+1} \dots s_r$. Två delsträngar betraktas som olika om och endast om de valda indexparen $(l, r)$ inte är desamma. Givet en sträng $s$ bestående av små bokstäver, beräkna först antalet CCPC-delsträngar i $s$. Därefter utförs $n$ operationer, där varje operation infogar en liten bokstav till vänster eller till höger om $s$. Du ska bestämma antalet CCPC-delsträngar i $s$ efter varje infogning.

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 100$), som anger antalet testfall.

För varje testfall innehåller den första raden en sträng $s$ ($4 \le |s| \le 5 \times 10^5$) bestående av små bokstäver, som representerar den ursprungliga strängen.

Den andra raden innehåller ett heltal $n$ ($1 \le n \le 5 \times 10^5$), som anger antalet operationer.

Den tredje raden innehåller $n$ strängar av längd $2$, $c_1, c_2, \dots, c_n$, separerade med mellanslag, som representerar operationerna i kronologisk ordning. För varje sträng $c_i$ är det första tecknet antingen L eller R, vilket anger att infogningen sker till vänster respektive till höger om $s$, och det andra tecknet är en liten bokstav som anger tecknet som ska infogas.

Det garanteras att varken summan av $|s|$ eller summan av $n$ över alla testfall överstiger $5 \times 10^5$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller $n + 1$ heltal separerade med mellanslag. Det första heltalet representerar svaret för den ursprungliga strängen, och det $(i + 1)$-te heltalet ($1 \le i \le n$) representerar svaret efter de första $i$ operationerna.

Exempel

Indata

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

Notering

För det andra testfallet blir $s$ efter alla operationer cccccpcpccppcppc. Dess CCPC-delsträngar inkluderar: $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}$.