A string $t$ of length $k$ consisting of lowercase letters is called a CCPC (Character-Character-Palindrome-Character) string if and only if the following conditions are met:

• $k \ge 4$;
• $t_1 = t_2 = t_k$;
• $t_3 t_4 \dots t_{k-1}$ is a palindrome.

A string of length $m$ is a palindrome if and only if for all $1 \le i \le m$, the $i$-th character of the string is equal to the $(m - i + 1)$-th character of the string.

For example, ccpc, ppap, zzzz, and aabcddcba are CCPC strings, while jinan, aaa, and oovoo are not.

A substring of a string $s$ can be represented by a pair of integers $(l, r)$ satisfying $1 \le l \le r \le |s|$, corresponding to the string $s_l s_{l+1} \dots s_r$. Two substrings are considered different if and only if the chosen pairs of indices $(l, r)$ are not the same. Given a string $s$ consisting of lowercase letters, first calculate the number of CCPC substrings in $s$. Then $n$ operations are applied, each inserting a lowercase letter on the left or right side of $s$. You need to determine the number of CCPC substrings in $s$ after each insertion.

Input

The first line contains an integer $T$ ($1 \le T \le 100$), indicating the number of test cases.

For each test case, the first line contains a string $s$ ($4 \le |s| \le 5 \times 10^5$) consisting of lowercase letters, representing the initial string.

The second line contains an integer $n$ ($1 \le n \le 5 \times 10^5$), indicating the number of operations.

The third line contains $n$ strings of length $2$, $c_1, c_2, \dots, c_n$, separated by spaces, representing the operations in chronological order. For each string $c_i$, the first character is either L or R, indicating that the insertion is on the left or right side of $s$, respectively, and the second character is a lowercase letter, indicating the character to be inserted.

It is guaranteed that neither the sum of $|s|$ nor the sum of $n$ over all test cases exceeds $5 \times 10^5$.

Output

For each test case, output a single line containing $n + 1$ integers separated by spaces. The first integer represents the answer for the initial string, and the $(i + 1)$-th integer ($1 \le i \le n$) represents the answer after the first $i$ operations.

Example

Input

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

Output

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

Note

For the second test case, after all operations, $s$ becomes cccccpcpccppcppc. Its CCPC substrings include: $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}$.