Рядок $t$ довжини $k$, що складається з малих латинських літер, називається рядком 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$ можна подати парою цілих чисел $(l, r)$, що задовольняють умову $1 \le l \le r \le |s|$, яка відповідає рядку $s_l s_{l+1} \dots s_r$. Два підрядки вважаються різними тоді й лише тоді, коли вибрані пари індексів $(l, r)$ не збігаються. Задано рядок $s$, що складається з малих літер; спочатку обчисліть кількість підрядків CCPC у $s$. Потім виконується $n$ операцій, кожна з яких вставляє малу літеру ліворуч або праворуч від $s$. Вам потрібно визначити кількість підрядків CCPC у $s$ після кожної вставки.

Вхідні дані

Перший рядок містить ціле число $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}$.