알파벳 소문자로 이루어진 길이 $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 부분 문자열의 개수를 구하세요. 그 후 $s$의 왼쪽 또는 오른쪽 끝에 알파벳 소문자를 하나 삽입하는 연산이 $n$번 수행됩니다. 각 삽입 연산 후에 $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$)이 주어집니다.

세 번째 줄에 시간 순서대로 연산을 나타내는 길이 $2$인 $n$개의 문자열 $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}$.