一個由小寫字母組成、長度為 $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}$。