Sebuah string $t$ dengan panjang $k$ yang terdiri dari huruf kecil disebut string CCPC (Character-Character-Palindrome-Character) jika dan hanya jika kondisi berikut terpenuhi:

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

Sebuah string dengan panjang $m$ adalah palindrom jika dan hanya jika untuk semua $1 \le i \le m$, karakter ke-$i$ dari string tersebut sama dengan karakter ke-$(m - i + 1)$ dari string tersebut.

Sebagai contoh, ccpc, ppap, zzzz, dan aabcddcba adalah string CCPC, sedangkan jinan, aaa, dan oovoo bukan.

Sebuah substring dari string $s$ dapat direpresentasikan oleh sepasang bilangan bulat $(l, r)$ yang memenuhi $1 \le l \le r \le |s|$, yang bersesuaian dengan string $s_l s_{l+1} \dots s_r$. Dua substring dianggap berbeda jika dan hanya jika pasangan indeks $(l, r)$ yang dipilih tidak sama. Diberikan sebuah string $s$ yang terdiri dari huruf kecil, pertama-tama hitunglah jumlah substring CCPC di dalam $s$. Kemudian $n$ operasi dilakukan, masing-masing menyisipkan sebuah huruf kecil di sisi kiri atau kanan $s$. Anda perlu menentukan jumlah substring CCPC di dalam $s$ setelah setiap penyisipan.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 100$), yang menyatakan jumlah kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah string $s$ ($4 \le |s| \le 5 \times 10^5$) yang terdiri dari huruf kecil, yang menyatakan string awal.

Baris kedua berisi sebuah bilangan bulat $n$ ($1 \le n \le 5 \times 10^5$), yang menyatakan jumlah operasi.

Baris ketiga berisi $n$ string dengan panjang $2$, $c_1, c_2, \dots, c_n$, dipisahkan oleh spasi, yang menyatakan operasi-operasi secara kronologis. Untuk setiap string $c_i$, karakter pertama adalah L atau R, yang masing-masing menunjukkan bahwa penyisipan dilakukan di sisi kiri atau kanan $s$, dan karakter kedua adalah huruf kecil yang menunjukkan karakter yang akan disisipkan.

Dijamin bahwa baik jumlah dari $|s|$ maupun jumlah dari $n$ di seluruh kasus uji tidak melebihi $5 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi $n + 1$ bilangan bulat yang dipisahkan oleh spasi. Bilangan bulat pertama menyatakan jawaban untuk string awal, dan bilangan bulat ke-$(i + 1)$ ($1 \le i \le n$) menyatakan jawaban setelah $i$ operasi pertama.

Contoh

Masukan

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

Keluaran

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

Catatan

Untuk kasus uji kedua, setelah semua operasi, $s$ menjadi cccccpcpccppcppc. Substring CCPC-nya meliputi: $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}$.