Let's call a string good if its length is at least $2$ and all of its characters are ${A}$ except for the last character which is ${B}$. The good strings are ${AB},{AAB},{AAAB},\ldots$. Note that ${B}$ is not a good string.

You are given an initially empty string $s_1$.

You can perform the following operation any number of times:

Choose any position of $s_1$ and insert some good string in that position.

Given a string $s_2$, can we turn $s_1$ into $s_2$ after some number of operations?


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single string $s_2$ ($1 \leq |s_2| \leq 2 \cdot 10^5$).

It is guaranteed that $s_2$ consists of only the characters ${A}$ and ${B}$.

It is guaranteed that the sum of $|s_2|$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print "YES" (without quotes) if we can turn $s_1$ into $s_2$ 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).


-----Examples-----

Input
4
AABAB
ABB
AAAAAAAAB
A
Output
YES
NO
YES
NO


-----Note-----

In the first test case, we transform $s_1$ as such: $\varnothing \to {{AAB}} \to {A}{{AB}}{AB}$.

In the third test case, we transform $s_1$ as such: $\varnothing \to {{AAAAAAAAB}}$.

In the second and fourth test case, it can be shown that it is impossible to turn $s_1$ into $s_2$.

Source: codeforces | Difficulty: EASY
Tags: Implementation

Constructive algorithms


Solutions:
import sys

def solve():
	inp = sys.stdin.readline
	s2 = inp().strip()
	if s2[-1] != 'B':
		print('NO')
		return
	c = 0
	for i in s2:
		if i == 'A':
			c += 1
		else:
			if c == 0:
				print('NO')
				return
			c -= 1
	print('YES')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


t = int(input())
out = ''
for _ in range(t):
	string = input()
	if len(string) < 2 or string[0] != 'A' or string[-1] != 'B':
		out += 'NO\n'
		continue
	countA = 0
	countB = 0
	for char in string:
		if char == 'A':
			countA += 1
		else:
			countB += 1
		if countB > countA:
			out += 'NO\n'
			break
	else:
		out += 'YES\n'
print(out)


def value(string):
	count_a = 0
	count_b = 0
	for j in range(len(string)):
		if string[j] == 'A':
			count_a += 1
		elif string[j] == 'B':
			count_b += 1
		if count_b > count_a:
			print('NO')
			break
	if count_b <= count_a:
		print('YES')

def main():
	n = int(input())
	strings = []
	for i in range(n):
		string = input()
		strings.append(string)
	for string in strings:
		if len(string) < 2 or string[-1] == 'A':
			print('NO')
		else:
			value(string)
main()


t = int(input())
res = []
for i in range(t):
	st = input()
	if len(st) <= 1 or st[len(st) - 1] != 'B':
		res.append('NO')
	else:
		flag = 1
		sum = 0
		for item in st:
			if item == 'A':
				sum = sum + 1
			else:
				sum = sum - 1
			if sum < 0:
				res.append('NO')
				flag = 0
				break
		if flag == 1:
			if sum >= 0:
				res.append('YES')
			else:
				res.append('NO')
for item in res:
	print(item)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input()[:-1]
	c = 0
	if s[-1] != 'B':
		print('NO')
	else:
		for i in s:
			if i == 'A':
				c += 1
			else:
				c -= 1
			if c < 0:
				print('NO')
				break
		else:
			print('YES')


def solve():
	s = input()
	bC = s.count('B')
	if bC > s.count('A'):
		return 'NO'
	if bC == 0:
		return 'NO'
	if s[0] == 'B' or s[-1] == 'A':
		return 'NO'
	balance = 0
	for i in range(len(s) - 1, -1, -1):
		if s[i] == 'B':
			balance += 1
		elif s[i] == 'A' and balance - 1 >= 0:
			balance -= 1
	if balance > 0:
		return 'NO'
	return 'YES'
t = int(input())
ans = []
for i in range(t):
	ans.append(solve())
for i in range(t):
	print(ans[i])


def main():

	def solve(s):
		r = 0
		for c in s:
			if c == 'A':
				r += 1
			else:
				r -= 1
				if r < 0:
					return 'NO'
		return 'YES' if s[-1] == 'B' else 'NO'
	t = int(input())
	ans = []
	for _ in range(t):
		s = input().strip()
		ans.append(solve(s))
	print('\n'.join(ans))
import sys, threading
input = sys.stdin.readline
thread = threading.Thread(target=main)
thread.start()
thread.join()


n = int(input())
out = []
for i in range(n):
	s = input()
	if len(s) < 2 or s[0] == 'B' or s[len(s) - 1] == 'A':
		out.append('NO')
		continue
	cA = 0
	cB = 0
	m = 0
	for i in range(len(s)):
		if s[i] == 'A':
			cA += 1
		elif s[i] == 'B':
			cB += 1
		if cA < cB:
			out.append('NO')
			m = 1
			break
	if m == 0:
		out.append('YES')
for i in out:
	print(i)


def solve_one():
	s = str(input())
	if s[-1] == 'A':
		return 'NO'
	num_a = 0
	num_b = 0
	for sym in s:
		if sym == 'A':
			num_a += 1
		if sym == 'B':
			num_b += 1
		if num_b > num_a:
			return 'NO'
	return 'YES'

def solve():
	t = int(input())
	anss = []
	for _ in range(t):
		anss.append(solve_one())
	for ans in anss:
		print(ans)
solve()


from re import S
import sys
sys.setrecursionlimit(10000)

def read_line(f):
	while True:
		s = f.readline().strip()
		if s:
			return s

def read_list(f):
	return [int(x) for x in read_line(f).split()]

def read_tuple(f):
	return tuple(read_list(f))

def load_single_case(f):
	return read_line(f)

def load_cases(f):
	n = int(f.readline())
	cases = []
	for _ in range(n):
		yield load_single_case(f)
	return cases

def solve(case):
	s = case
	if s[-1] != 'B':
		return False
	l = 0
	for c in s:
		if c == 'A':
			l += 1
		elif l == 0:
			return False
		else:
			l -= 1
	return True

def outcome_string(outcome):
	return 'YES' if outcome else 'NO'

def save_outcomes(f, outcomes):
	for (n, o) in enumerate(outcomes):
		f.write('{}\n'.format(outcome_string(o)))

def process(path_in=None, path_out=None):
	if path_out is None and path_in is not None:
		path_out = path_in.rsplit('.', 1)[0] + '.out'
	f_in = open(path_in) if path_in else sys.stdin
	f_out = open(path_out, 'w') if path_out else sys.stdout
	try:
		outcomes = [solve(c) for c in load_cases(f_in)]
		save_outcomes(f_out, outcomes)
	finally:
		if path_in:
			f_in.close()
		if path_out:
			f_out.close()
process()


import sys
lines = []
for line in sys.stdin:
	if line == '\n':
		break
	lines.append(line.strip())
n_cases = lines.pop(0)
for line in lines:
	solution = 'YES'
	length = len(line)
	if line[0] == 'B':
		solution = 'NO'
	elif line[length - 1] == 'A':
		solution = 'NO'
	else:
		a_count = 0
		b_count = 0
		for i in range(0, len(line)):
			if line[i] == 'A':
				a_count += 1
			else:
				b_count += 1
			if a_count < b_count:
				solution = 'NO'
				break
	print(solution)


import math
import sys
import itertools
import fractions
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
GAP = 1
for t in [wtf[i:i + GAP] for i in range(1, len(wtf), GAP)]:
	S = t[0]
	if S[-1] != 'B':
		print('NO')
		continue
	while 'AB' in S:
		S = S.replace('AB', '')
	if 'B' not in S:
		print('YES')
	else:
		print('NO')


n = int(input())
L = []
for i in range(n):
	x = input()
	L.append(x)
for i in range(n):
	s = L[i]
	size = len(s)
	count = 0
	wrong = 0
	for j in range(size):
		if s[j] == 'B':
			count = count + 1
			if count * 2 > j + 1:
				wrong = 1
				break
	if wrong == 1 or count == 0 or s[size - 1] == 'A':
		print('NO')
	else:
		print('YES')


n = int(input())
ma = []
for i in range(n):
	x = input()
	k = 0
	if x[-1] == 'B' and x[0] == 'A':
		for j in x:
			if j == 'A':
				k += 1
			if j == 'B':
				k -= 1
			if k < 0:
				ma.append('NO')
				break
		if k >= 0:
			ma.append('YES')
	else:
		ma.append('NO')
for i in ma:
	print(i)


t = int(input())
ans = []
for i in range(t):
	s = input()
	a = 0
	b = 0
	if len(s) >= 2 and s[-1] != 'A':
		k = 1
		for j in range(len(s)):
			if s[j] == 'A':
				a += 1
			else:
				b += 1
				if b > a:
					k = 0
					break
		if k:
			ans.append('YES')
		else:
			ans.append('NO')
	else:
		ans.append('NO')
for elem in ans:
	print(elem)


n = int(input())
a = []
for i in range(n):
	a.append(input())
for i in range(n):
	k = a[i]
	if len(k) >= 2 and k[0] == 'A' and (k[-1] == 'B'):
		BCOUNT = 0
		aCoUnT = 0
		flag = 0
		for i in range(len(k)):
			if k[i] == 'B':
				BCOUNT += 1
				if BCOUNT > aCoUnT:
					flag = 1
			else:
				aCoUnT += 1
		if flag:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


t = int(input())
l = []
for i in range(t):
	l.append(input())
for s in l:
	if len(s) == 1:
		print('NO')
		continue
	x = []
	x += s
	f = True
	if x.count('A') == 0 or x.count('B') == 0 or x[0] == 'B' or (x[len(x) - 1] == 'A'):
		f = False
	else:
		c = 0
		for i in x:
			c += 1 if i == 'A' else -1
			if c < 0:
				f = False
				break
	if f:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	s2 = input()
	isPossible = True
	l = len(s2)
	if l < 2 or s2[-1] == 'A' or s2[0] == 'B':
		isPossible = False
	else:
		num_A = 0
		num_B = 0
		for i in range(l):
			if s2[i] == 'A':
				num_A += 1
			else:
				num_B += 1
				if num_A < num_B:
					isPossible = False
					break
	if isPossible:
		print('YES')
	else:
		print('NO')


def f(string):
	(a_count, b_count) = (0, 0)
	for i in range(len(string)):
		if string[i] == 'A':
			a_count += 1
		else:
			b_count += 1
		if a_count < b_count:
			return 'NO'
	return 'YES'
for _ in range(int(input())):
	string = input()
	if string[-1] == 'A' or len(string) < 2:
		print('NO')
	else:
		print(f(string))


t = int(input())

def solve():
	s = input()
	l = len(s)
	c = 0
	r = 1
	if s[l - 1] == 'B':
		for k in s:
			if k == 'A':
				c += 1
			else:
				c -= 1
			if c < 0:
				print('NO')
				r = 0
				break
		if r:
			print('YES')
	else:
		print('NO')
for i in range(t):
	solve()


import sys
for i in range(int(sys.stdin.readline())):
	p = ''
	stack = []
	st = list(sys.stdin.readline().rstrip('\n'))
	ck = True
	for i in st:
		if i == 'B':
			if not stack:
				ck = False
				break
			stack.pop()
		else:
			stack.append(1)
	if st[-1] != 'B' or not ck:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	flag = True
	if len(s) < 2:
		print('NO')
		continue
	if s[-1] != 'B' or s[0] != 'A':
		print('NO')
		continue
	ca = 0
	cb = 0
	for i in s:
		if i == 'B':
			cb += 1
		else:
			ca += 1
		if cb > ca:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input()
	a = 0
	b = 0
	for i in range(len(s) - 1):
		if s[i] == 'A':
			a = a + 1
		else:
			b = b + 1
		if b > a:
			print('NO')
			break
	else:
		if a > 0 and b > 0 and (s[-2] == 'B'):
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	s = input()
	if s[-1] == 'A' or s[0] == 'B':
		print('NO')
		continue
	a = 0
	b = 0
	for i in s:
		if i == 'A':
			a += 1
		else:
			b += 1
		if a < b:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for _ in range(t):
	s2 = input()
	(a, b) = (0, 0)
	for c in s2:
		if c == 'A':
			a += 1
		else:
			b += 1
		if a < b:
			print('NO')
			break
	else:
		print('YES' if a and b and (s2[-1] == 'B') else 'NO')


for _ in range(int(input())):
	s = input()
	yn = False
	if s[-1] == 'B':
		while True:
			s1 = s.replace('AB', '')
			if s1 == s:
				break
			s = s1
		if s == '':
			yn = True
		if 'B' not in set([ch for ch in s]):
			yn = True
	print('YES' if yn else 'NO')


for _ in range(int(input())):
	s = input()
	(a, b) = (0, 0)
	ans = True
	if 'B' == s[0] or 'A' == s[-1]:
		print('NO')
	else:
		for i in s:
			if i == 'A':
				a += 1
			else:
				b += 1
			if a < b:
				ans = False
		print('YES' if ans else 'NO')


for _ in range(int(input())):
	s = input()
	c = 0
	f = 1
	for i in s:
		if i == 'A':
			c += 1
		else:
			c -= 1
		if c < 0:
			f = 0
			break
	if f and s[0] == 'A' and (s[-1] == 'B'):
		print('YES')
	else:
		print('NO')


T = int(input())
for case in range(T):
	st = input()
	total_a = 0
	if st[-1] == 'A':
		print('NO')
		continue
	for chr in st:
		if chr == 'A':
			total_a += 1
		else:
			total_a -= 1
		if total_a < 0:
			print('NO')
			break
	else:
		print('YES')


n = int(input())
for _ in range(n):
	s = input()
	a = 0
	b = 0
	state = True
	if len(s) > 1 and s[0] == 'A' and (s[-1] == 'B'):
		for i in s:
			if i == 'A':
				a += 1
			else:
				b += 1
			if a < b:
				print('NO')
				state = False
				break
		if state:
			print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = input()
	if n[-1] == 'A' or n[0] == 'B':
		print('NO')
	else:
		i = 0
		for a in n[::-1]:
			if a == 'B':
				i += 1
			else:
				i = (i > 1) * (i - 1)
		if i == 0:
			print('YES')
		else:
			print('NO')


def sol():
	n = int(input())
	for i in range(n):
		s = input()
		if s == 'A' or s == 'B' or s[-1] != 'B':
			print('NO')
			continue
		a = 0
		b = 0
		val = 'y'
		for j in s:
			if j == 'A':
				a += 1
			else:
				b += 1
			if a < b:
				print('NO')
				val = 'n'
				break
		if val == 'y':
			print('YES')
sol()


t = int(input())
i = 0
for _ in range(t):
	s = input()
	a = 0
	b = 0
	if s[-1] == 'A':
		print('NO')
	else:
		for j in s:
			if j == 'A':
				a += 1
			else:
				b += 1
			if a < b:
				print('NO')
				break
		if a >= b:
			print('YES')


num_cases = int(input())
for i in range(num_cases):
	s2 = input()
	valid = True
	if s2[len(s2) - 1] == 'A' or len(s2) < 2 or s2[0] == 'B':
		valid = False
	if valid:
		(a, b) = (0, 0)
		for char in s2:
			if char == 'A':
				a += 1
			else:
				b += 1
			if b > a:
				valid = False
				break
	if valid:
		print('YES')
	else:
		print('NO')


t = int(input())
for j in range(t):
	s = input()
	if len(s) == 1 or s[0] == 'B' or s[-1] == 'A' or (s.count('B') > s.count('A')):
		print('NO')
	else:
		f = 0
		count_B = 0
		count_A = 0
		for i in range(0, len(s)):
			if s[i] == 'B':
				count_B += 1
			else:
				count_A += 1
			if count_A < count_B:
				f = -1
				break
		if f == 0:
			print('YES')
		else:
			print('NO')


def solution(s):
	if s.endswith('A'):
		return 'NO'
	ans = 0
	for c in s:
		if c == 'A':
			ans += 1
		else:
			ans -= 1
			if ans < 0:
				return 'NO'
	return 'YES'
for t in range(0, int(input())):
	s = input()
	print(solution(s))


n = int(input())
for j in range(n):
	s = input()
	flag = 0
	if s[0] == 'B':
		flag = 1
	if s[-1] != 'B':
		flag = 1
	ac = 0
	bc = 0
	for i in s:
		if i == 'A':
			ac += 1
		if i == 'B':
			bc += 1
		if bc > ac:
			flag = 1
			break
	if flag == 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	a = input()
	f = 0
	ka = 0
	kb = 0
	if a[-1] == 'A':
		print('NO')
		continue
	for i in range(len(a)):
		if kb > ka:
			print('NO')
			f += 1
			break
		if a[i] == 'A':
			ka += 1
		else:
			kb += 1
	if kb > ka and f == 0:
		print('NO')
		f += 1
	if f == 0:
		print('YES')


for i in range(int(input())):
	s = input()
	x = 0
	y = 0
	ans = 'YES'
	if ('A' not in s or s[0] == 'B') or ('B' not in s or s[-1] == 'A'):
		print('NO')
		continue
	for i in s:
		if i == 'A':
			x += 1
		else:
			y += 1
		if y > x:
			ans = 'NO'
			break
	print(ans)


for _ in range(int(input())):
	x = input()
	a = 0
	b = 0
	p = 'YES'
	if x[-1] == 'A' or x[0] == 'B':
		p = 'NO'
	else:
		for i in x:
			if i == 'A':
				a += 1
			else:
				b += 1
			if a < b:
				p = 'NO'
				break
	print(p)


import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(int(input())):
	s = insr()
	n = len(s)
	if n != s.count('A') + s.count('B') or s.count('A') == 0 or s.count('B') == 0:
		print('NO')
		continue
	prev = s[0]
	last = s[-1]
	if prev != 'A' or last != 'B':
		print('NO')
		continue
	ass = 0
	bs = 0
	for i in s:
		if i == 'A':
			ass += 1
		else:
			bs += 1
		if ass < bs:
			print('NO')
			break
	else:
		print('YES')


t = int(input())

def solve(s):
	cnt = 0
	n_dels = 0
	for c in s:
		if c == 'B':
			if cnt > 0:
				cnt -= 1
				n_dels += 1
			else:
				return 'NO'
		else:
			cnt += 1
	if n_dels == 0 or s[-1] == 'A':
		return 'NO'
	else:
		return 'YES'
for i in range(t):
	s = input()
	print(solve(s))


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def main():
	for _ in range(int(input())):
		s = input()
		ok = True
		if len(s) == 1:
			print('NO')
		else:
			n = len(s)
			(a, b) = (0, 0)
			for i in range(n):
				if s[i] == 'A':
					a += 1
				else:
					b += 1
					if a >= b:
						a -= 1
						b -= 1
					else:
						ok = False
						break
			if s[-1] == 'A':
				ok = False
			if a == n and b == 0:
				ok = False
			print('YES' if ok else 'NO')
main()


import math
for i in range(int(input())):
	s = input()
	a = 0
	b = 0
	c = len(s)
	if c < 2 or s[0] == 'B' or s[c - 1] == 'A':
		print('NO')
	else:
		res = 'YES'
		for i in range(c):
			if s[i] == 'A':
				a += 1
			elif s[i] == 'B':
				b += 1
			if b > a:
				res = 'NO'
				break
		print(res)


def solve(s):
	(ca, cb) = (0, 0)
	if len(s) < 2 or s[len(s) - 1] != 'B':
		return 'NO'
	for c in s:
		if c == 'A':
			ca += 1
		else:
			cb += 1
			if cb > ca:
				return 'NO'
	return 'YES'
t = int(input())
for i in range(t):
	s = input()
	print(solve(s))


from collections import Counter, deque, defaultdict
from math import *
from bisect import bisect_right
mod = 1000000007

def solve():
	s = input()
	n = len(s)
	if n < 2:
		print('NO')
		return
	acount = 0
	bcount = 0
	for i in s:
		if i == 'A':
			acount += 1
		else:
			bcount += 1
			if acount < bcount:
				print('NO')
				return
	if s[-1] != 'B':
		print('NO')
		return
	print('YES')
t = int(input())
for num in range(t):
	solve()


def solve(a):
	c = 0
	f = 0
	for i in range(len(a)):
		if a[i] == 'A':
			c += 1
		elif a[i] == 'B':
			c -= 1
		if c < 0:
			f = 1
	if c < 0 or f == 1:
		return 'NO'
	else:
		return 'YES'
for _ in range(int(input())):
	s = input()
	if len(s) < 2 or s[0] == 'B' or s[-1] == 'A':
		print('NO')
	elif s.count('B') > s.count('A'):
		print('NO')
	else:
		b = solve(s)
		print(b)


for _ in range(int(input())):
	l = list(input())
	x = 0
	for i in l:
		if i == 'A':
			x += 1
		else:
			x -= 1
			if x < 0:
				print('NO')
				break
	else:
		if l[-1] == 'A':
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	s = input()
	if len(s) == 1 or s[0] == 'B' or s[-1] == 'A':
		print('NO')
		continue
	while 'AB' in s:
		s = s.replace('AB', '')
	if 'B' in s:
		print('NO')
	else:
		print('YES')


def main():
	T = int(input())
	for _ in range(T):
		s = input()
		get_result(s)

def get_result(s):
	cnt = 0
	if s[-1] == 'A':
		print('NO')
		return
	gar = len(s)
	i = 0
	printed = False
	while i < gar and cnt >= 0:
		if s[i] == 'A':
			cnt += 1
		else:
			cnt -= 1
		i += 1
	if cnt >= 0:
		print('YES')
		return
	else:
		print('NO')
		return
main()


import sys
input = sys.stdin.readline

def LS():
	return list(input().rstrip())
t = int(input())
for i in range(t):
	s = LS()
	len_s = len(s)
	count = 0
	flag = False
	if s[-1] == 'B':
		flag = True
	for i in range(len_s):
		if s[i] == 'A':
			count += 1
		else:
			count -= 1
		if count < 0:
			flag = False
	if flag:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	a = input()
	if a[0] != 'A' or a[-1] != 'B' or a.count('A') < a.count('B'):
		print('NO')
	else:
		b = 0
		c = 1
		for j in range(len(a)):
			if a[j] == 'A':
				b += 1
			elif a[j] == 'B':
				b -= 1
			if b < 0:
				c = 0
				break
		print('YES' if c else 'NO')


for i in range(int(input())):
	a = list(input())
	if a[0] == 'B' or a[-1] != 'B':
		print('NO')
	else:
		c = 0
		for i in a:
			if i == 'A':
				c += 1
			else:
				c -= 1
			if c < 0:
				break
		if c >= 0:
			print('YES')
		else:
			print('NO')


a = int(input())
for x in range(a):
	b = input()
	j = len(b)
	if j == 1:
		print('NO')
	elif b[0] == 'B':
		print('NO')
	elif b[-1] == 'A':
		print('No')
	else:
		t = 0
		l = 0
		for z in range(j):
			if b[z] == 'B':
				l -= 1
			else:
				l += 1
			if l < 0:
				t = -1
				break
		if t == -1:
			print('NO')
		else:
			print('YES')


def solve():
	s = input()
	flag = True
	a = 0
	for i in range(len(s)):
		if s[i] == 'B':
			if a == 0:
				flag = False
				break
			else:
				a -= 1
		else:
			a += 1
	if flag and s[len(s) - 1] == 'B':
		print('YES')
	else:
		print('NO')
t = int(input())
while t:
	solve()
	t -= 1


class Util:
	ALLOWED_LOCAL_FILES = set(['main.py', 'A.py', 'B.py', 'C.py', 'D.py', 'E.py', 'F.py', 'G.py'])
	MOD = 1000000000 + 7

	@staticmethod
	def get_int_list_input():
		return list(map(int, input().split()))

	@staticmethod
	def p(yes=False):
		print('YES') if yes else print('NO')

def solve():
	s = input()
	a_count = 0
	b_count = 0
	if s[-1] == 'A':
		Util.p()
		return
	for c in s:
		if c == 'A':
			a_count += 1
		else:
			b_count += 1
		if b_count > a_count:
			Util.p()
			return
	Util.p(True)

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		solve()
import sys
if sys.argv[0] in Util.ALLOWED_LOCAL_FILES:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
main()


for _ in range(int(input())):
	S = input()
	c = 0
	for i in S:
		if i == 'A':
			c += 1
		else:
			c -= 1
			if c < 0:
				print('NO')
				break
	else:
		if S[-1] == 'B':
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	s = input().strip()
	if s[-1] == 'A':
		valid = False
	else:
		(c, valid) = (0, True)
		for x in s:
			if x == 'A':
				c += 1
			else:
				c -= 1
			if c < 0:
				valid = False
				break
	if valid:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = input()
	count = 0
	for i in n:
		if i == 'A':
			count += 1
		else:
			count -= 1
			if count < 0:
				print('NO')
				break
	else:
		if n[-1] == 'B':
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	s2 = input()
	flag = True
	if s2[-1] == 'A' or s2[0] == 'B' or len(s2) < 2:
		flag = False
	else:
		A_count = 0
		B_count = 0
		for i in s2:
			if i == 'A':
				A_count += 1
			elif i == 'B':
				B_count += 1
			if A_count < B_count:
				flag = False
				break
	if flag:
		print('YES')
	else:
		print('NO')


nt = int(input())
for _ in range(nt):
	counter = 0
	flagb = 0
	flaga = 0
	s2 = input()
	l = len(s2)
	if l >= 2:
		if s2[0] != 'A' or s2[-1] != 'B':
			print('NO')
			continue
	for i in range(l - 1, -1, -1):
		ch = s2[i]
		if ch == 'B':
			flagb = 1
			counter += 1
		else:
			flaga = 1
			if counter != 0:
				counter -= 1
	if flaga == 0 or flagb == 0 or counter != 0:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	t = input()
	a = b = 0
	if t[-1] != 'B':
		print('NO')
		continue
	for e in t:
		if e == 'A':
			a += 1
		elif e == 'B':
			b += 1
		if b > a:
			print('NO')
			break
	else:
		print('YES')


import sys
input = sys.stdin.readline
for _ in range(int(input().rstrip())):
	s = input().rstrip()
	answer = 'YES'
	if len(s) == 1:
		answer = 'NO'
	else:
		stack = []
		i = 0
		while i < len(s):
			if s[i] == 'B':
				if stack:
					stack.pop()
				else:
					break
			else:
				stack.append('A')
			i += 1
		if i != len(s) or s[-1] == 'A':
			answer = 'NO'
	print(answer)


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	bdetect = 0
	if s[0] == 'A' and s[-1] == 'B':
		for j in range(n):
			if s[n - 1 - j] == 'B':
				bdetect += 1
			elif bdetect > 0:
				bdetect -= 1
		if bdetect == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for t in range(int(input())):
	s = input()
	sum = 0
	flag = True
	for char in s:
		sum += 1 if char == 'A' else -1
		if sum < 0:
			flag = False
			break
	if len(s) < 2 or s[0] == 'B' or s[-1] == 'A' or (flag == False):
		print('NO')
	else:
		print('YES')


def solve(s):
	if s[0] == 'B' or s[-1] == 'A':
		return 'NO'
	while True:
		s = s.replace('AB', '')
		if not s or all((c == 'A' for c in s)):
			return 'YES'
		if s[0] == 'B':
			return 'NO'
for _ in range(int(input())):
	s = input()
	print(solve(s))


t = int(input())
for i in range(t):
	s2 = input()
	if len(s2) == 1:
		print('NO')
		continue
	if s2[0] == 'B':
		print('NO')
		continue
	if s2[::-1][0] == 'A':
		print('NO')
		continue
	b_arr = []
	for c in s2[::-1]:
		if c == 'B':
			b_arr.append(c)
		if c == 'A':
			if len(b_arr) > 0:
				b_arr.pop(0)
	if len(b_arr) == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	a = 0
	ans = 'YES'
	for i in s:
		if i == 'A':
			a += 1
		else:
			a -= 1
		if a < 0:
			ans = 'NO'
			break
	print(ans if s[-1] == 'B' else 'NO')


t = int(input())
while t > 0:
	s = input()
	(a, b) = (0, 0)
	for i in s:
		if i == 'A':
			a += 1
		else:
			b += 1
		if a < b:
			print('NO')
			break
	else:
		if a and b and (s[-1] == 'B'):
			print('YES')
		else:
			print('NO')
	t -= 1


a = int(input())
for i in range(a):
	b = input()
	while True:
		if b[len(b) - 1] == 'A':
			print('NO')
			break
		if b[0] == 'B':
			print('NO')
			break
		count = 0
		for j in b:
			if j == 'A':
				count = count + 1
			else:
				count = count - 1
			if count < 0:
				print('NO')
				break
		if count >= 0:
			print('YES')
			break
		break


trials = int(input())
for trial in range(trials):
	s = list(input())
	s.reverse()
	b = 0
	if len(s) >= 2 and s[-1] == 'A' and (s[0] == 'B'):
		for i in s:
			if i == 'B':
				b += 1
			elif i == 'A' and b > 0:
				b -= 1
		if b == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	if not 'A' in s or not 'B' in s or s[len(s) - 1] != 'B':
		print('NO')
		continue
	while True:
		same = s
		s = s.replace('AB', '')
		if s == '':
			print('YES')
			break
		elif not 'A' in s:
			print('NO')
			break
		elif not 'B' in s:
			print('YES')
			break
		elif same == s:
			if 'BA' in s:
				print('NO')
				break


def solve():
	s = input()
	(numA, numB) = (0, 0)
	if s[-1] == 'A':
		return False
	for i in range(len(s)):
		if s[i] == 'B':
			numB += 1
			if numB > numA:
				return False
		else:
			numA += 1
	if numB > 0:
		return True
	else:
		return False
t = int(input())
while t > 0:
	t -= 1
	if solve():
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	s = input()
	d = 0 if s[-1] == 'B' else -42
	for c in s:
		d += 1 if c == 'A' else -1
		if d < 0:
			break
	print('YES' if d >= 0 else 'NO')


def solve():
	s = input()
	if len(s) < 2:
		print('NO')
		return
	if s.startswith('B') or s.endswith('A'):
		print('NO')
		return
	ac = 0
	bc = 0
	for i in range(len(s)):
		if s[i] == 'A':
			ac += 1
		else:
			bc += 1
		if bc > ac:
			print('NO')
			return
	print('YES')
	return
for l in range(int(input())):
	solve()


for _ in range(int(input())):
	a = 0
	for x in input():
		if x == 'A':
			a += 1
		else:
			a -= 1
		if a < 0:
			print('NO')
			break
	else:
		print('YES' if x == 'B' else 'NO')


def solve(s):
	if len(s) < 2:
		return 'NO'
	if s[-1] == 'A':
		return 'NO'
	ans = []
	for i in s:
		if len(ans) == 0 and i == 'B':
			return 'NO'
		if i == 'A':
			ans.append(i)
		if i == 'B':
			ans.pop()
	if len(ans) == 0 or ans[-1] == 'A':
		return 'YES'
	return 'NO'
t = int(input())
for _ in range(t):
	s = input()
	print(solve(s))


for i in range(int(input())):
	s = input()
	if s[-1] != 'B':
		print('NO')
		continue
	flag = 1
	cnt = 0
	for i in s:
		if i == 'A':
			cnt += 1
		elif cnt == 0:
			flag = 0
			break
		else:
			cnt -= 1
	if flag:
		print('YES')
	else:
		print('NO')


def solve(s, l):
	if s[0] == 'B' or s[-1] == 'A':
		return 'NO'
	else:
		count = 0
		for x in s:
			if x == 'A':
				count += 1
			else:
				count -= 1
				if count < 0:
					return 'NO'
		return 'YES'
t = int(input())
for _ in range(t):
	s = input()
	l = len(s)
	ans = solve(s, l)
	print(ans)


def rep(n: str):
	x = True
	while x:
		n = n.replace('AB', '')
		if 'AB' not in n:
			x = False
	return n
t = int(input())
for _ in range(t):
	s = input()
	if 'AB' in s and s[-1] == 'B':
		s = rep(s)
		if s.replace('A', '') == '':
			print('YES')
		else:
			print('NO')
	else:
		print('NO')