英小文字からなる長さ $k$ の文字列 $t$ が次の条件をすべて満たすとき、またそのときに限り、$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 は CCPC 文字列ではありません。

文字列 $s$ の部分文字列は、$1 \le l \le r \le |s|$ を満たす整数の組 $(l, r)$ によって表され、文字列 $s_l s_{l+1} \dots s_r$ に対応します。$2$ つの部分文字列は、選ばれた添字の組 $(l, r)$ が異なるとき、またそのときに限り異なるとみなされます。英小文字からなる文字列 $s$ が与えられるので、まず $s$ に含まれる CCPC 部分文字列の個数を求めてください。その後、$s$ の左端または右端に英小文字を $1$ 文字挿入する操作が $n$ 回行われます。各挿入操作の後に、$s$ に含まれる CCPC 部分文字列の個数を求めてください。

入力

最初の行には、テストケースの数を表す整数 $T$ ($1 \le T \le 100$) が与えられます。

各テストケースについて、最初の行には初期文字列を表す英小文字からなる文字列 $s$ ($4 \le |s| \le 5 \times 10^5$) が与えられます。

$2$ 行目には、操作の回数を表す整数 $n$ ($1 \le n \le 5 \times 10^5$) が与えられます。

$3$ 行目には、時系列順の操作を表す長さ $2$ の $n$ 個の文字列 $c_1, c_2, \dots, c_n$ が空白区切りで与えられます。各文字列 $c_i$ の $1$ 文字目は L または R であり、それぞれ $s$ の左端または右端への挿入を表し、$2$ 文字目は挿入される英小文字を表します。

すべてのテストケースにおける $|s|$ の総和および $n$ の総和はいずれも $5 \times 10^5$ を超えないことが保証されます。

出力

各テストケースについて、空白で区切られた $n + 1$ 個の整数を $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

ノート

$2$ 番目のテストケースでは、すべての操作の後に $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}$。