如果一个字符串的长度至少为 $$$2$$$ 并且其所有字符都是 $$$\texttt{A}$$$(最后一个字符是 $$$\texttt{B}$$$),那么我们称这个字符串为好字符串。好的字符串是 $$$\texttt{AB}、\texttt{AAB}、\texttt{AAAB}、\ldots$$$。请注意,$$$\texttt{B}$$$ 不是一个好的字符串。
给你一个最初为空的字符串$$$s_1$$$。
您可以多次执行以下操作:
- 选择 $$$s_1$$$ 的任意位置并在该位置插入一些好的字符串。
给定一个字符串$$$s_2$$$,我们可以在经过一定次数的操作后将$$$s_1$$$转换为$$$s_2$$$吗?
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个字符串 $$$s_2$$$ ($$$1 \leq |s_2| \leq 2 \cdot 10^5$$$)。
保证 $$$s_2$$$ 仅包含字符 $$$\texttt{A}$$$ 和 $$$\texttt{B}$$$。
保证所有测试用例的 $$$|s_2|$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果经过一定次数的操作后我们可以将 $$$s_1$$$ 转换为 $$$s_2$$$,则打印“YES”(不带引号),否则打印“NO”(不带引号)。
在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。
示例
输入 #1
4 AABAB ABB AAAAAAAAB A
输出 #1
YES NO YES NO
注意
在第一个测试用例中,我们将 $$$s_1$$$ 转换为: $$$\varnothing \to \color{red}{\texttt{AAB}} \to \texttt{A}\color{red}{\texttt{AB}}\texttt{AB}$$$。
在第三个测试用例中,我们将 $$$s_1$$$ 转换为:$$$\varnothing \to \color{red}{\texttt{AAAAAAAAB}}$$$。
在第二个和第四个测试用例中,可以表明不可能将 $$$s_1$$$ 转换为 $$$s_2$$$。