让我们调用一个字符串$$$t$$$ 交替 如果对于从 $$$1$$$ 到 $$$n - 1$$$ 的每个 $$$i$$$,条件 $$$t_{i} \neq t_{i + 1}$$$ 成立。
给你一个字符串 $$$s$$$ 仅包含字母 "a“和/或”b“。您可以对其进行以下操作 最多一次:
- 选择一个子串 $$$s_{l}s_{l+1}\ldots s_{r}$$$ 至少包含一个字符;
- 选择子串后,可以将其中的所有字母反转,即改变每个“a“到”b“以及每个”b“到”a”(允许你这样做,但你不必这样做);
- 反转所选子串,即将字符串 $$$s_{1}s_{2}\dots s_{l-1}s_{l}s_{l+1}\ldots s_{r}s_{r+1}\ldots s_{n}$$$ 转换为 $$$s_{1}s_{2}\dots s_{l-1}s_{r}s_{r-1}\ldots s_{l}s_{r+1}\ldots s_{n}$$$。
请注意,执行此类操作时,不需要执行第二步。例如,对于字符串 $$$s =~$$$"贝贝“,一次操作后即可获得”贝巴巴" 通过选择子字符串 $$$s_{5}s_{6}s_{7}$$$ 并执行第二步,或 "巴巴巴布" 通过选择子字符串 $$$s_{1}s_{2}s_{3}s_{4}$$$ 并且不执行第二步。但是,您始终必须执行操作的第三步。
你的任务是确定是否可以获得任何 交替 字符串,来自字符串 $$$s$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例由一行组成,其中包含一个字符串 $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^{5}$$$)。该字符串仅包含小写拉丁字母“a“和/或”b".
输入的附加限制:
- 所有测试用例的字符串长度总和不超过 $$$2 \cdot 10^{5}$$$。
输出
对于每个测试用例,输出以下内容之一:
- 是,如果可以获得 交替 来自 $$$s$$$ 的字符串;
- NO 否则。
您可以在任何情况下输出每个字母。
示例
输入复制
8abbabaaaaaabababbaababbaabbabbbababaaabb
输出复制
YESNOYESYESNOYESYESYES
注意
在第一个示例中,您可以选择子字符串 $$$s_3 s_4 s_5 s_6$$$ 并跳过第二步;然后你得到字符串“贝贝".
在第三个示例中,您可以选择子字符串 $$$s_1 s_2 s_3 s_4 s_5$$$ 并执行第二步;然后你得到字符串“贝巴巴".
在第四个示例中,字符串已经是交替的。
在第六个示例中,您可以选择子字符串$$$s_2$$$并执行第二步;然后你得到字符串“宝贝".