一個由小寫字母組成、長度為 $k$ 嘅字串 $t$ 被稱為 CCPC（Character-Character-Palindrome-Character）字串，當且僅當滿足以下條件：

• $k \ge 4$；
• $t_1 = t_2 = t_k$；
• $t_3 t_4 \dots t_{k-1}$ 係一個回文字串。

一個長度為 $m$ 嘅字串係回文字串，當且僅當對於所有 $1 \le i \le m$，該字串嘅第 $i$ 個字符等於第 $(m - i + 1)$ 個字符。

例如，ccpc、ppap、zzzz 同 aabcddcba 係 CCPC 字串，而 jinan、aaa 同 oovoo 唔係。

字串 $s$ 嘅一個子串可以用一對滿足 $1 \le l \le r \le |s|$ 嘅整數 $(l, r)$ 表示，對應字串 $s_l s_{l+1} \dots s_r$。兩個子串被視為唔同，當且僅當所揀嘅下標對 $(l, r)$ 唔相同。畀定一個由小寫字母組成嘅字串 $s$，首先計算 $s$ 中 CCPC 子串嘅數量。之後會進行 $n$ 次操作，每次喺 $s$ 嘅左邊或者右邊插入一個小寫字母。你需要求出每次插入後 $s$ 中 CCPC 子串嘅數量。

輸入格式

第一行包含一個整數 $T$（$1 \le T \le 100$），表示測試數據組數。

對於每組測試數據，第一行包含一個由小寫字母組成嘅字串 $s$（$4 \le |s| \le 5 \times 10^5$），表示初始字串。

第二行包含一個整數 $n$（$1 \le n \le 5 \times 10^5$），表示操作次數。

第三行包含 $n$ 個長度為 $2$ 嘅字串 $c_1, c_2, \dots, c_n$，由空格分隔，按時間順序表示各次操作。對於每個字串 $c_i$，第一個字符係 L 或者 R，分別表示喺 $s$ 嘅左邊或者右邊進行插入，第二個字符係一個小寫字母，表示要插入嘅字符。

保證所有測試數據中 $|s|$ 嘅總和同 $n$ 嘅總和都唔超過 $5 \times 10^5$。

輸出格式

對於每組測試數據，輸出一行包含 $n + 1$ 個由空格分隔嘅整數。第一個整數表示初始字串嘅答案，第 $(i + 1)$ 個整數（$1 \le i \le n$）表示前 $i$ 次操作後嘅答案。

範例

輸入

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

輸出

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

提示

對於第二組測試數據，喺所有操作之後，$s$ 變成 cccccpcpccppcppc。佢嘅 CCPC 子串包括：$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}$。