Eine Zeichenkette $t$ der Länge $k$, die aus Kleinbuchstaben besteht, wird genau dann als CCPC-Zeichenkette (Character-Character-Palindrome-Character) bezeichnet, wenn die folgenden Bedingungen erfüllt sind:

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

Eine Zeichenkette der Länge $m$ ist genau dann ein Palindrom, wenn für alle $1 \le i \le m$ das $i$-te Zeichen der Zeichenkette gleich dem $(m - i + 1)$-ten Zeichen der Zeichenkette ist.

Beispielsweise sind ccpc, ppap, zzzz und aabcddcba CCPC-Zeichenketten, während jinan, aaa und oovoo keine sind.

Eine Teilzeichenkette einer Zeichenkette $s$ kann durch ein Paar ganzer Zahlen $(l, r)$ mit $1 \le l \le r \le |s|$ dargestellt werden, was der Zeichenkette $s_l s_{l+1} \dots s_r$ entspricht. Zwei Teilzeichenketten gelten genau dann als verschieden, wenn die gewählten Indexpaare $(l, r)$ nicht identisch sind. Gegeben ist eine aus Kleinbuchstaben bestehende Zeichenkette $s$. Berechnen Sie zunächst die Anzahl der CCPC-Teilzeichenketten in $s$. Anschließend werden $n$ Operationen ausgeführt, bei denen jeweils ein Kleinbuchstabe am linken oder rechten Ende von $s$ eingefügt wird. Sie müssen nach jedem Einfügen die Anzahl der CCPC-Teilzeichenketten in $s$ bestimmen.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 100$), die Anzahl der Testfälle.

Für jeden Testfall enthält die erste Zeile eine aus Kleinbuchstaben bestehende Zeichenkette $s$ ($4 \le |s| \le 5 \times 10^5$), die die anfängliche Zeichenkette darstellt.

Die zweite Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 5 \times 10^5$), die Anzahl der Operationen.

Die dritte Zeile enthält $n$ durch Leerzeichen getrennte Zeichenketten der Länge $2$, $c_1, c_2, \dots, c_n$, die die Operationen in chronologischer Reihenfolge darstellen. Für jede Zeichenkette $c_i$ ist das erste Zeichen entweder L oder R, was angibt, dass am linken bzw. rechten Ende von $s$ eingefügt wird, und das zweite Zeichen ist ein Kleinbuchstabe, der das einzufügende Zeichen angibt.

Es wird garantiert, dass über alle Testfälle hinweg weder die Summe von $|s|$ noch die Summe von $n$ den Wert $5 \times 10^5$ überschreitet.

Ausgabe

Geben Sie für jeden Testfall eine einzige Zeile mit $n + 1$ durch Leerzeichen getrennten ganzen Zahlen aus. Die erste ganze Zahl gibt die Antwort für die anfängliche Zeichenkette an, und die $(i + 1)$-te ganze Zahl ($1 \le i \le n$) gibt die Antwort nach den ersten $i$ Operationen an.

Beispiel

Eingabe

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

Ausgabe

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

Hinweis

Für den zweiten Testfall wird $s$ nach allen Operationen zu cccccpcpccppcppc. Seine CCPC-Teilzeichenketten umfassen: $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}$.