题目描述

我们称一个字符串 $t$ 是“交替的”，如果对于 $1$ 到 $n-1$ 的每个 $i$，均满足 $t_i \neq t_{i+1}$。

给定一个仅包含字符 a 和/或 b 的字符串 $s$。你最多可以对该字符串执行一次以下操作：

1. 选择一个至少包含一个字符的子串 $s_l s_{l+1} \dots s_r$；
2. 在选择子串后，你可以选择是否将其中的所有字母进行反转（即把所有的 a 变为 b，把所有的 b 变为 a）；
3. 将选定的子串进行翻转（即将字符串 $s_1 s_2 \dots s_{l-1} s_l s_{l+1} \dots s_r s_{r+1} \dots s_n$ 变换为 $s_1 s_2 \dots s_{l-1} s_r s_{r-1} \dots s_l s_{r+1} \dots s_n$）。

注意：执行操作时，你不一定要进行第二步（反转字母），但必须执行第三步（翻转子串）。例如，对于字符串 $s = \text{ababbab}$，通过选择子串 $s_5 s_6 s_7$ 并执行第二步，可以得到 $\text{abababa}$；通过选择子串 $s_1 s_2 s_3 s_4$ 且不执行第二步，可以得到 $\text{bababab}$。

请判断是否能够通过上述至多一次操作，使字符串 $s$ 变为一个“交替”字符串。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例包含一行，为一个字符串 $s$（$2 \le |s| \le 2 \cdot 10^5$）。字符串仅包含小写拉丁字母 a 和/或 b。

所有测试用例中字符串长度之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，如果能够从 $s$ 得到交替字符串，输出 YES；否则输出 NO。

样例输入 1

8
abbaba
aaaaa
bababba
ab
abbaabba
bbb
ababa
aabb

样例输出 1

YES
NO
YES
YES
NO
YES
YES
YES

说明

样例解释

• 在第一个样例中，可以选择子串 $s_3 s_4 s_5 s_6$ 并不执行第二步，即可得到字符串 $\text{ababab}$。
• 在第三个样例中，可以选择子串 $s_1 s_2 s_3 s_4 s_5$ 并执行第二步，即可得到字符串 $\text{abababa}$。
• 在第四个样例中，字符串本身已经是交替的。
• 在第六个样例中，可以选择子串 $s_2$ 并执行第二步，即可得到字符串 $\text{bab}$。

数据范围

对于所有测试点，保证：

• $1 \le t \le 10^4$。
• $2 \le |s| \le 2 \cdot 10^5$。
• 所有测试用例中字符串长度之和不超过 $2 \cdot 10^5$。