Una stringa $t$ di lunghezza $k$ composta da lettere minuscole è chiamata stringa CCPC (Character-Character-Palindrome-Character) se e solo se sono soddisfatte le seguenti condizioni:

• $k \ge 4$;
• $t_1 = t_2 = t_k$;
• $t_3 t_4 \dots t_{k-1}$ è un palindromo.

Una stringa di lunghezza $m$ è un palindromo se e solo se per ogni $1 \le i \le m$, l'$i$-esimo carattere della stringa è uguale al $(m - i + 1)$-esimo carattere della stringa.

Ad esempio, ccpc, ppap, zzzz e aabcddcba sono stringhe CCPC, mentre jinan, aaa e oovoo non lo sono.

Una sottostringa di una stringa $s$ può essere rappresentata da una coppia di interi $(l, r)$ che soddisfano $1 \le l \le r \le |s|$, corrispondente alla stringa $s_l s_{l+1} \dots s_r$. Due sottostringhe sono considerate diverse se e solo se le coppie di indici $(l, r)$ scelte non sono uguali. Data una stringa $s$ composta da lettere minuscole, calcola innanzitutto il numero di sottostringhe CCPC in $s$. Successivamente vengono applicate $n$ operazioni, ciascuna delle quali inserisce una lettera minuscola a sinistra o a destra di $s$. Devi determinare il numero di sottostringhe CCPC in $s$ dopo ogni inserimento.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 100$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga contiene una stringa $s$ ($4 \le |s| \le 5 \times 10^5$) composta da lettere minuscole, che rappresenta la stringa iniziale.

La seconda riga contiene un intero $n$ ($1 \le n \le 5 \times 10^5$), che indica il numero di operazioni.

La terza riga contiene $n$ stringhe di lunghezza $2$, $c_1, c_2, \dots, c_n$, separate da spazi, che rappresentano le operazioni in ordine cronologico. Per ogni stringa $c_i$, il primo carattere è L oppure R, indicando rispettivamente che l'inserimento avviene a sinistra o a destra di $s$, e il secondo carattere è una lettera minuscola che indica il carattere da inserire.

È garantito che né la somma di $|s|$ né la somma di $n$ su tutti i casi di test superano $5 \times 10^5$.

Output

Per ogni caso di test, stampa una singola riga contenente $n + 1$ interi separati da spazi. Il primo intero rappresenta la risposta per la stringa iniziale, e l'$(i + 1)$-esimo intero ($1 \le i \le n$) rappresenta la risposta dopo le prime $i$ operazioni.

Esempio

Input

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

Output

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

Nota

Per il secondo caso di test, dopo tutte le operazioni, $s$ diventa cccccpcpccppcppc. Le sue sottostringhe CCPC includono: $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}$.