B. Alternating String
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Let us call a string $$$t$$$ alternating if for every $$$i$$$ from $$$1$$$ to $$$n - 1$$$, the condition $$$t_{i} \neq t_{i + 1}$$$ holds.

You are given a string $$$s$$$ consisting only of the letters "a" and/or "b". You may perform the following operation on it at most once:

  • choose a substring $$$s_{l}s_{l+1}\ldots s_{r}$$$ consisting of at least one character;
  • after choosing the substring, you may invert all letters in it, that is, change every "a" to "b" and every "b" to "a" (you are allowed to do it, but you don't have to do it);
  • reverse the chosen substring, that is, transform the string $$$s_{1}s_{2}\dots s_{l-1}s_{l}s_{l+1}\ldots s_{r}s_{r+1}\ldots s_{n}$$$ into $$$s_{1}s_{2}\dots s_{l-1}s_{r}s_{r-1}\ldots s_{l}s_{r+1}\ldots s_{n}$$$.

Note that when performing such an operation, you are not required to do the second step. For example, for the string $$$s =~$$$"ababbab", after one operation you can obtain "abababa" by choosing the substring $$$s_{5}s_{6}s_{7}$$$ and doing the second step, or "bababab" by choosing the substring $$$s_{1}s_{2}s_{3}s_{4}$$$ and not doing the second step. However, you always have to perform the third step of the operation.

Your task is to determine whether it is possible to obtain any alternating string from the string $$$s$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

Each test case consists of one line containing one string $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^{5}$$$). The string consists only of lowercase Latin letters "a" and/or "b".

Additional constraints on the input:

  • the sum of string lengths over all test cases does not exceed $$$2 \cdot 10^{5}$$$.
Output

For each test case, output one of the following:

  • YES, if it is possible to obtain an alternating string from $$$s$$$;
  • NO otherwise.

You may output each letter in any case.

Example
Input
8
abbaba
aaaaa
bababba
ab
abbaabba
bbb
ababa
aabb
Output
YES
NO
YES
YES
NO
YES
YES
YES
Note

In the first example, you can choose the substring $$$s_3 s_4 s_5 s_6$$$ and skip the second step; then you get the string "ababab".

In the third example, you can choose the substring $$$s_1 s_2 s_3 s_4 s_5$$$ and perform the second step; then you get the string "abababa".

In the fourth example, the string is already alternating.

In the sixth example, you can choose the substring $$$s_2$$$ and perform the second step; then you get the string "bab".