Một xâu $t$ độ dài $k$ gồm các chữ cái thường được gọi là xâu CCPC (Character-Character-Palindrome-Character) khi và chỉ khi thỏa mãn các điều kiện sau:

• $k \ge 4$;
• $t_1 = t_2 = t_k$;
• $t_3 t_4 \dots t_{k-1}$ là một xâu đối xứng.

Một xâu độ dài $m$ là xâu đối xứng khi và chỉ khi với mọi $1 \le i \le m$, ký tự thứ $i$ của xâu bằng ký tự thứ $(m - i + 1)$ của xâu.

Ví dụ, ccpc, ppap, zzzz và aabcddcba là các xâu CCPC, trong khi jinan, aaa và oovoo thì không.

Một xâu con của xâu $s$ có thể được biểu diễn bởi một cặp số nguyên $(l, r)$ thỏa mãn $1 \le l \le r \le |s|$, tương ứng với xâu $s_l s_{l+1} \dots s_r$. Hai xâu con được coi là khác nhau khi và chỉ khi cặp chỉ số $(l, r)$ được chọn là không giống nhau. Cho một xâu $s$ gồm các chữ cái thường, trước tiên hãy tính số lượng xâu con CCPC trong $s$. Sau đó có $n$ thao tác được thực hiện, mỗi thao tác chèn một chữ cái thường vào bên trái hoặc bên phải của $s$. Bạn cần xác định số lượng xâu con CCPC trong $s$ sau mỗi lần chèn.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 100$), cho biết số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa một xâu $s$ ($4 \le |s| \le 5 \times 10^5$) gồm các chữ cái thường, biểu thị xâu ban đầu.

Dòng thứ hai chứa một số nguyên $n$ ($1 \le n \le 5 \times 10^5$), cho biết số lượng thao tác.

Dòng thứ ba chứa $n$ xâu độ dài $2$, $c_1, c_2, \dots, c_n$, cách nhau bởi dấu cách, biểu thị các thao tác theo thứ tự thời gian. Với mỗi xâu $c_i$, ký tự đầu tiên là L hoặc R, tương ứng cho biết việc chèn được thực hiện ở bên trái hoặc bên phải của $s$, và ký tự thứ hai là một chữ cái thường cho biết ký tự được chèn.

Dữ liệu đảm bảo tổng của $|s|$ cũng như tổng của $n$ trong tất cả các bộ dữ liệu đều không vượt quá $5 \times 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng gồm $n + 1$ số nguyên cách nhau bởi dấu cách. Số nguyên đầu tiên biểu thị đáp án cho xâu ban đầu, và số nguyên thứ $(i + 1)$ ($1 \le i \le n$) biểu thị đáp án sau $i$ thao tác đầu tiên.

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

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

Ghi chú

Đối với bộ dữ liệu thứ hai, sau tất cả các thao tác, $s$ trở thành cccccpcpccppcppc. Các xâu con CCPC của nó bao gồm: $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}$.