Napis $t$ o długości $k$, składający się z małych liter, nazywamy napisem CCPC (Character-Character-Palindrome-Character) wtedy i tylko wtedy, gdy spełnione są następujące warunki:

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

Napis o długości $m$ jest palindromem wtedy i tylko wtedy, gdy dla każdego $1 \le i \le m$, $i$-ty znak napisu jest równy $(m - i + 1)$-szemu znakowi napisu.

Na przykład ccpc, ppap, zzzz oraz aabcddcba są napisami CCPC, natomiast jinan, aaa oraz oovoo nie są.

Podciąg spójny (podsłowo) napisu $s$ można przedstawić jako parę liczb całkowitych $(l, r)$ spełniających $1 \le l \le r \le |s|$, odpowiadającą napisowi $s_l s_{l+1} \dots s_r$. Dwa podsłowa uznajemy za różne wtedy i tylko wtedy, gdy wybrane pary indeksów $(l, r)$ nie są takie same. Dla danego napisu $s$ składającego się z małych liter najpierw oblicz liczbę podsłów CCPC w $s$. Następnie wykonywanych jest $n$ operacji, z których każda wstawia małą literę z lewej lub z prawej strony napisu $s$. Musisz wyznaczyć liczbę podsłów CCPC w $s$ po każdym wstawieniu.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 100$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera napis $s$ ($4 \le |s| \le 5 \times 10^5$) składający się z małych liter, reprezentujący początkowy napis.

Drugi wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 5 \times 10^5$), oznaczającą liczbę operacji.

Trzeci wiersz zawiera $n$ napisów o długości $2$, $c_1, c_2, \dots, c_n$, oddzielonych spacjami, reprezentujących operacje w kolejności chronologicznej. Dla każdego napisu $c_i$ pierwszy znak to L lub R, co oznacza wstawienie odpowiednio z lewej lub z prawej strony napisu $s$, a drugi znak to mała litera oznaczająca wstawiany znak.

Gwarantowane jest, że ani suma $|s|$, ani suma $n$ po wszystkich przypadkach testowych nie przekracza $5 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający $n + 1$ liczb całkowitych oddzielonych spacjami. Pierwsza liczba całkowita oznacza odpowiedź dla początkowego napisu, a $(i + 1)$-sza liczba całkowita ($1 \le i \le n$) oznacza odpowiedź po pierwszych $i$ operacjach.

Przykład

Wejście

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

Wyjście

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

Uwaga

Dla drugiego przypadku testowego po wszystkich operacjach napis $s$ staje się równy cccccpcpccppcppc. Jego podsłowa CCPC to: $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}$.