[Solution] I love AAAB solution codeforces

I love AAAB solution codeforces – Let’s call a string good if its length is at least 22 and all of its characters are 𝙰A except for the last character which is 𝙱B. The good strings are 𝙰𝙱,𝙰𝙰𝙱,𝙰𝙰𝙰𝙱,AB,AAB,AAAB,…. Note that 𝙱B is not a good string.

[Solution] I love AAAB solution codeforces

You are given an initially empty string 𝑠1s1.

You can perform the following operation any number of times:

• Choose any position of 𝑠1s1 and insert some good string in that position.

Given a string 𝑠2s2, can we turn 𝑠1s1 into 𝑠2s2 after some number of operations?

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single string 𝑠2s2 (1|𝑠2|21051≤|s2|≤2⋅105).

It is guaranteed that 𝑠2s2 consists of only the characters 𝙰A and 𝙱B.

It is guaranteed that the sum of |𝑠2||s2| over all test cases does not exceed 21052⋅105.

[Solution] I love AAAB solution codeforces

For each test case, print “YES” (without quotes) if we can turn 𝑠1s1 into 𝑠2s2 after some number of operations, and “NO” (without quotes) otherwise.

You can output “YES” and “NO” in any case (for example, strings “yEs“, “yes” and “Yes” will be recognized as a positive response).

Example

input

Copy
4
AABAB
ABB
AAAAAAAAB
A


output

Copy
YES
NO
YES
NO


I love AAAB solution codeforces

In the first test case, we transform 𝑠1s1 as such: 𝙰𝙰𝙱𝙰𝙰𝙱𝙰𝙱∅→AAB→AABAB.

In the third test case, we transform 𝑠1s1 as such: 𝙰𝙰𝙰𝙰𝙰𝙰𝙰𝙰𝙱∅→AAAAAAAAB.

In the second and fourth test case, it can be shown that it is impossible to turn 𝑠1s1 into 𝑠2s2.