题目描述

RIBBIT!

《祖玛》是一款经典的益智消除游戏。玩家控制一只石青蛙，通过发射彩球来消除轨道上连续的同色彩球。

• 射击后，射击位置的同色球之和 $≥3$ 则会被消除。
• 消除后，若当次被消除的彩球两端有同色的球则会被牵引。牵引后，若牵引处的同色球之和 $≥3$ 则会被消除。

东哥现在给定你一个由大写字母组成的序列，表示轨道上的彩球排列。以及一个射击位置。你需要计算在该位置发射指定颜色彩球后，最多能消除多少个彩球。

输入格式

第一行包含一个整数 $T\ (1 ≤ T ≤ 2*10^5)$，表示测试用例的数量。

每组测试用例包含两行：

• 第一行是一个由大写字母组成的字符串 $S\ (1 ≤ |S| ≤ 2*10^5)$ ，表示初始彩球序列，下标从 $1$ 到 $|S|$。
• 第二行是一个整数 $P$ $(0 ≤ P ≤ |S|)$ 和一个大写字母 $C$，表示射击位置和发射的彩球颜色。$P=0$ 表示在序列最前面插入，$P=|S|$ 表示在序列最后面插入。

题目保证 $\sum |S| ≤ 2*10^5$。

输出格式

对于每组测试用例，输出一个整数，表示在该射击位置发射彩球后最多能消除的彩球数量（包括射击的彩球）。

3
BBBAAAAZZZ
0 B
AABBAA
2 B
ZIME
1 I

4
7
0