You work in the quality control department of technical support for a large company. Your job is to make sure all client issues have been resolved.

Today you need to check a copy of a dialog between a client and a technical support manager. According to the rules of work, each message of the client must be followed by one or several messages, which are the answer of a support manager. However, sometimes clients ask questions so quickly that some of the manager's answers to old questions appear after the client has asked some new questions.

Due to the privacy policy, the full text of messages is not available to you, only the order of messages is visible, as well as the type of each message: a customer question or a response from the technical support manager. It is guaranteed that the dialog begins with the question of the client.

You have to determine, if this dialog may correspond to the rules of work described above, or the rules are certainly breached.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). Description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 100$) — the total number of messages in the dialog.

The second line of each test case consists of $n$ characters "Q" and "A", describing types of messages in the dialog in chronological order. Character "Q" denotes the message with client question, and character "A" — the message with technical support manager answer. It is guaranteed that the first character in the line equals to "Q".


-----Output-----

For each test case print "Yes" (without quotes) if dialog may correspond to the rules of work, or "No" (without quotes) otherwise.


-----Examples-----

Input
5
4
QQAA
4
QQAQ
3
QAA
1
Q
14
QAQQAQAAQQQAAA
Output
Yes
No
Yes
No
Yes


-----Note-----

In the first test case the two questions from the client are followed with two specialist's answers. So this dialog may correspond to the rules of work.

In the second test case one of the first two questions was not answered.

In the third test case the technical support manager sent two messaged as the answer to the only message of the client.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in range(n):
		if s[i] == 'Q':
			c = c + 1
		elif c == 0:
			c = 0
		else:
			c = c - 1
	if c != 0:
		print('No')
	else:
		print('Yes')


input = __import__('sys').stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	stack = []
	for i in range(n):
		if s[i] == 'Q':
			stack.append('Q')
		try:
			if s[i] == 'A':
				stack.pop()
		except IndexError:
			continue
	if stack:
		print('No')
	else:
		print('Yes')


def check():
	n = int(input())
	s = input()
	count = 0
	for i in range(len(s)):
		if s[i] == 'Q':
			count += 1
		elif count >= 1:
			count -= 1
	if count == 0:
		print('Yes')
	else:
		print('No')

def main():
	test_cases = int(input())
	for i in range(test_cases):
		check()
main()


def function(t, s):
	Q = 0
	for i in s:
		if i == 'A':
			if Q > 0:
				Q -= 1
		elif i == 'Q':
			Q += 1
	return 'Yes' if Q <= 0 else 'No'
l = int(input())
while l > 0:
	l -= 1
	n = int(input())
	s = input()
	print(function(n, s))


t = int(input())
list = []
for i in range(t):
	w = int(input())
	QA = input()
	count = 0
	for e in QA:
		if e == 'Q':
			count += 1
		elif count > 0:
			count -= 1
	if count == 0:
		list.append('Yes')
	else:
		list.append('No')
for e in list:
	print(e)


input_count = int(input())
result = ''
for _ in range(input_count):
	qa_count = int(input())
	qa = input()
	q_count = 0
	for char in qa:
		if char == 'Q':
			q_count += 1
		elif char == 'A' and q_count > 0:
			q_count -= 1
	if q_count == 0:
		result += 'Yes\n'
	else:
		result += 'No\n'
print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	a = 0
	valid = True
	for i in range(n - 1, -1, -1):
		if s[i] == 'A':
			a += 1
		else:
			if a == 0:
				valid = False
				break
			a -= 1
	if valid:
		print('Yes')
	else:
		print('No')


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	q = 0
	a = 0
	for i in s:
		if i == 'Q':
			q += 1
		else:
			q -= 1
			if q < 0:
				q = 0
	if q > 0:
		print('No')
	else:
		print('Yes')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	x = 0
	for i in s:
		if i == 'Q':
			x += 1
		else:
			x = max(0, x - 1)
	if x == 0:
		print('Yes')
	else:
		print('No')


def check(arr):
	tot = 0
	for i in arr:
		if i == 'Q':
			if tot < 0:
				tot = 0
			tot += 1
		else:
			tot -= 1
	if tot <= 0:
		print('Yes')
	else:
		print('No')
t = int(input())
for _ in range(t):
	n = input()
	arr = input()
	check(arr)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(cq, ca) = (0, 0)
	didnt = False
	for c in reversed(s):
		if c == 'Q':
			cq += 1
		else:
			ca += 1
		if cq > ca:
			print('No')
			didnt = True
			break
	if not didnt:
		print('Yes')


num = int(input(''))
while num:
	num = num - 1
	w = int(input(''))
	b = input('')
	flag = 0
	if b[0] == 'A' or b[-1] == 'Q':
		flag = 1
		print('No')
	else:
		for (index, each_char) in enumerate(b):
			n = w - index
			if each_char == 'Q':
				q = b[index:].count('Q')
				a = n - q
				if q > a:
					flag = 1
					print('No')
					break
				else:
					pass
			else:
				pass
	if flag == 0:
		print('Yes')


for _ in range(int(input())):
	k = int(input())
	s = input()
	if s[-1] != 'A':
		print('No')
		continue
	ix = 0
	yi = 0
	checkjbdshjdhbjsdjk = 0
	for i in range(k - 1, -1, -1):
		if s[i] == 'A':
			yi += 1
		else:
			ix += 1
		if ix > yi:
			print('No')
			checkjbdshjdhbjsdjk = 1
			break
	if not checkjbdshjdhbjsdjk:
		print('Yes')


t = int(input(''))
for i in range(t):
	n = int(input(''))
	s = input('')
	a = 0
	q = 0
	e = 0
	for i in range(n - 1, -1, -1):
		if s[i] == 'Q':
			q += 1
		else:
			a += 1
		if q > a:
			print('No')
			e = 1
			break
	if e == 0:
		print('Yes')


def func(n, s):
	count = 0
	for ch in s:
		count += 1 if ch == 'Q' else -1
		count = max(0, count)
	return count == 0
T = int(input())
for _ in range(T):
	n = int(input())
	s = list(input())
	print('Yes' if func(n, s) else 'No')


class Sol:

	def pattern(self, string):
		count = 0
		for i in string:
			if i == 'Q':
				count = count - 1
			else:
				count = count + 1
			count = min(count, 0)
		if count < 0:
			print('No')
		else:
			print('Yes')
obj = Sol()
testcases = int(input())
for i in range(testcases):
	length = int(input())
	string = input()
	obj.pattern(string)


def solve():
	_ = int(input())
	t = input()
	ctn = 0
	for i in t:
		if i == 'Q':
			ctn += 1
		else:
			ctn -= 1
		if ctn < 0:
			ctn = 0
	return 'Yes' if ctn == 0 else 'No'
t = int(input())
for _ in range(t):
	print(solve())


N = int(input())
cases = []
for i in range(N):
	cases.append([int(input()), input()])

def main():
	for case in cases:
		l = case[0]
		dialog = case[1]
		Qs = 0
		for i in range(l):
			if dialog[i] == 'Q':
				Qs += 1
			elif dialog[i] == 'A':
				if Qs >= 1:
					Qs -= 1
				else:
					Qs = 0
		if Qs == 0:
			print('Yes')
		else:
			print('No')
main()


t = input()
t = int(t)
answers = []
for i in range(t):
	n = input()
	n = int(n)
	aq = 0
	messages = input()
	for j in range(n):
		if messages[j] == 'Q':
			aq += 1
		elif aq != 0:
			aq -= 1
	answers.append('Yes' if aq == 0 else 'No')
for i in range(t):
	print(answers[i])


def solve(n, string):
	if string[0] != 'Q':
		return 'No'
	a = 0
	q = 0
	for c in string[::-1]:
		if c == 'Q':
			q += 1
		elif c == 'A':
			a += 1
		if q > a:
			return 'No'
	return 'Yes'

def main():
	for t in range(int(input())):
		n = int(input())
		string = input()
		print(solve(n, string))
main()


for t in [*open(0)][2::2]:
	c = 0
	for x in t[:-1]:
		c = max(0, c + 2 * (x > 'A') - 1)
	print('YNeos'[c > 0::2])


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	k = 0
	for j in range(len(s)):
		if s[j] == 'Q':
			k += 1
		else:
			k -= 1
			if k < 0:
				k = 0
	if k > 0:
		print('No')
	else:
		print('Yes')


start = int(input())
a = 0
q = 0
for x in range(start):
	a = 0
	q = 0
	how_many = int(input())
	text = input()
	text = text.lower()
	for x in range(how_many):
		if text[x] == 'a':
			if q > 0:
				q = q - 1
		else:
			q += 1
	if q == 0:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	n = int(input())
	count = 0
	inpt = input()
	for chr in inpt:
		if chr == 'Q':
			count += 1
		elif chr == 'A':
			count -= 1
		if count < 0:
			count = 0
	if count == 0:
		print('Yes')
	else:
		print('No')


testCases = int(input())
results = []
for i in range(testCases):
	num = int(input())
	QA = ''
	Q = []
	while len(QA) < num:
		QA = input()
	for j in QA:
		if j == 'Q':
			Q.append(j)
		elif len(Q) != 0:
			Q.pop()
	if len(Q) > 0:
		results.append('No')
	else:
		results.append('Yes')
for res in results:
	print(res)


n = int(input())
a = []
for i in range(n):
	l = int(input())
	b = input()
	q = b.count('Q')
	aa = b.count('A')
	h = 0
	if q <= aa and b[-1] != 'Q':
		for j in range(len(b)):
			if b[j] == 'Q':
				h += 1
			else:
				h -= 1
			if h < 0:
				h = 0
		if h == 0:
			a.append('Yes')
		else:
			a.append('No')
	else:
		a.append('No')
for i in a:
	print(i, end='\n')


import sys
input = sys.stdin.readline

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

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	S = readStr()
	cnt = 0
	for i in range(n - 1, -1, -1):
		if S[i] == 'A':
			cnt += 1
		else:
			cnt -= 1
			if cnt < 0:
				return 'No'
	return 'Yes'
for _ in range(int(input())):
	print(solve())


for i in range(int(input())):
	n = int(input())
	s = list(input())
	l = []
	for i in s:
		if i == 'Q':
			l.append('a')
		if i == 'A' and len(l) > 0:
			l.pop(-1)
	if len(l) == 0:
		print('Yes')
	else:
		print('No')


t = int(input())
for x in range(t):
	num = 0
	n = int(input())
	dialog = input()
	for i in range(n):
		if dialog[-i - 1] == 'A':
			num += 1
		else:
			num -= 1
		if num < 0:
			print('No')
			break
		if i == n - 1 and num >= 0:
			print('Yes')


t = int(input())
num = 0
while num < t:
	n = input()
	if 'Q' not in n and 'A' not in n:
		pass
	else:
		num += 1
		count = 0
		for i in n:
			if i == 'Q':
				count += 1
			elif count > 0:
				count -= 1
		if count == 0:
			print('Yes')
		else:
			print('No')


cases = int(input())
outputs = []
for i in range(cases):
	n = int(input())
	messages = input()
	count = 0
	doubleup = False
	for j in range(n):
		if messages[j] == 'Q':
			count += 1
		if messages[j] == 'A':
			if count == 0:
				continue
			else:
				count -= 1
	if count > 0:
		outputs.append('No')
	else:
		outputs.append('Yes')
for i in range(len(outputs)):
	print(outputs[i])


import math
for i in range(int(input())):
	a = int(input())
	string = str(input())
	bol = True
	if string[-1] == 'Q':
		bol = False
	elif list(string).count('A') < math.ceil(a / 2):
		bol = False
	else:
		pass
	if bol:
		listt = []
		counter = 1
		for i in range(len(string) - 1):
			if string[i] == string[i + 1]:
				counter += 1
			else:
				listt.append(counter)
				counter = 1
		listt.append(len(string) - sum(listt))
		dp1 = 0
		dp2 = 0
		for i in range(len(listt) // 2 - 1, -1, -1):
			dp1 += listt[2 * i + 1]
			dp2 += listt[2 * i]
			if dp1 < dp2:
				bol = False
				break
			else:
				pass
	if bol:
		print('Yes')
	else:
		print('No')


def solve():
	n = int(input())
	s = list(input())
	if s[n - 1] == 'Q':
		print('No')
	else:
		ot = 'Yes'
		i = n - 2
		l = [0, 1]
		while i >= 0:
			if s[i] == 'Q':
				l[0] += 1
			else:
				l[1] += 1
			if l[0] > l[1]:
				ot = 'No'
			i -= 1
		print(ot)
t = int(input())
while t > 0:
	solve()
	t -= 1


for i in range(int(input())):
	n = int(input())
	stri = input()
	count = 0
	for i in range(n):
		if stri[i] == 'Q':
			count += 1
		if stri[i] == 'A':
			count = 0 if count < 1 else count - 1
	print('YNeos'[count > 0::2])


t = int(input())
for i in range(t):
	n = int(input())
	msg = input()
	x = 0
	for letter in msg:
		if letter == 'Q':
			x += 1
		else:
			x = max(0, x - 1)
	if x == 0:
		print('Yes')
	else:
		print('No')


n = int(input())
d = []
for i in range(n):
	len_ = int(input())
	res = input()
	if len_ == 1:
		d.append('No')
		continue
	k = 0
	c = ''
	for i in res[::-1]:
		if i == 'Q':
			k -= 1
		if i == 'A':
			k += 1
		if k < 0:
			break
	if k >= 0:
		c = 'Yes'
	else:
		c = 'No'
	d.append(c)
for i in d:
	print(i)


class Solution:

	def solve(n: int, line: str):
		q_lst = []
		for i in range(n):
			if line[i] == 'Q':
				q_lst.append('Q')
				continue
			if q_lst:
				q_lst.pop()
		if not q_lst:
			return 'Yes'
		return 'No'

	def technicalSupp():
		for i in range(int(input())):
			num_line = int(input())
			line = input()
			print(Solution.solve(num_line, line))
Solution.technicalSupp()


for x in range(int(input())):
	n = int(input())
	s = input()
	q = 0
	if s[0] == 'A':
		print('NO')
	else:
		for i in s:
			if i == 'Q':
				q += 1
			elif q > 0:
				q -= 1
		if q <= 0:
			print('Yes')
		else:
			print('No')


n = int(input())
ans = []
for i in range(n):
	stack = []
	m = int(input())
	ask = list(input())
	for j in range(m):
		if ask[j] == 'Q':
			stack.append('Q')
		elif len(stack) > 0:
			stack.pop()
	ans.append('Yes' if stack.count('Q') == 0 else 'No')
for i in ans:
	print(i)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = a[::-1]
	A_count = 0
	Q_count = 0
	for i in b:
		if i == 'Q':
			Q_count += 1
		else:
			A_count += 1
		if Q_count > A_count:
			print('No')
			break
	else:
		print('Yes')


n = int(input())
lis = []
for _ in range(n):
	k = int(input())
	s = input()
	count = 0
	for i in range(k):
		if s[i] == 'Q':
			count -= 1
		elif s[i] == 'A' and count < 0:
			count += 1
	if count >= 0:
		lis.append('Yes')
	else:
		lis.append('No')
for elem in lis:
	print(elem)


t = int(input())
for i in range(t):
	n = int(input())
	st = input()
	lst = len(st)
	stri = st[::-1]
	cra = 0
	crq = 0
	flag = 0
	for i in range(lst):
		if stri[i] == 'A':
			cra += 1
		else:
			cra -= 1
		if cra < 0:
			print('No')
			flag = 1
			break
	if flag == 0:
		print('Yes')


test = int(input())
for i in range(test):
	queue_count = int(input())
	queue = input()
	q_count = 0
	for i in queue:
		if i == 'Q':
			q_count += 1
		elif q_count > 0:
			q_count -= 1
	if q_count == 0:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	qa = input()
	count = 0
	for i in range(0, len(qa)):
		if qa[i] == 'Q':
			count += 1
		elif count > 0:
			count -= 1
	if count > 0:
		print('No')
	else:
		print('Yes')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	count_Q = 0
	count_A = 0
	for i in range(n):
		if s[i] == 'Q':
			count_Q += 1
		else:
			count_Q -= 1
			if count_Q <= 0:
				count_Q = 0
	if count_Q == 0:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	n = int(input())
	jada = str(input())
	jada_list = [str(x) for x in jada]
	if jada.count('Q') > jada.count('A') or jada[-1] == 'Q':
		print('No')
	else:
		b = True
		jada_list.reverse()
		Q = 0
		A = 0
		for i in jada_list:
			if i == 'Q':
				Q += 1
			else:
				A += 1
			if Q > A:
				print('No')
				b = False
				break
		if b:
			print('Yes')


for i in range(int(input())):
	num = int(input())
	a = list(input())
	t = 0
	for i in range(len(a) - 1, -1, -1):
		if a[i] == 'A':
			t += 1
		else:
			t -= 1
			if t < 0:
				break
	if t < 0:
		print('No')
	else:
		print('Yes')


def solve():
	t = int(input())
	while t:
		t -= 1
		n = int(input())
		str = input()
		q = 0
		for i in range(len(str)):
			if str[i] == 'Q':
				q += 1
			elif q != 0:
				q -= 1
		if q == 0:
			print('Yes')
		else:
			print('No')
solve()


t = int(input())
for n in range(t):
	n = int(input())
	s = input()
	count = 0
	for letter in s:
		if letter == 'A' and (not count):
			continue
		if letter == 'Q':
			count += 1
		else:
			count -= 1
	if count > 0:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	n = int(input())
	t = list(input())
	k = 0
	for x in t:
		if x == 'Q':
			k += 1
		elif k > 0:
			k -= 1
	if k == 0:
		print('Yes')
	else:
		print('No')


def solution(dialog):
	state = 0
	for ch in dialog:
		if ch == 'Q':
			state += 1
		elif state > 0:
			state -= 1
	if state == 0:
		print('Yes')
	else:
		print('No')
	return
t = int(input())
for i in range(t):
	n = int(input())
	tx = input()
	solution(tx)


noOfTestCases = input()
charTestCase = []
testCase = []
cnt = 0
for i in range(0, int(noOfTestCases)):
	charTestCase.append(input())
	testCase.append(input())
for testcases in testCase:
	for chr in testcases:
		if chr.upper() == 'Q':
			cnt = cnt + 1
		elif chr.upper() == 'A':
			if cnt > 0:
				cnt = cnt - 1
	if cnt > 0:
		print('No')
	else:
		print('Yes')
	cnt = 0


T = int(input())
for _ in range(T):
	n = int(input())
	s = input()
	p = 0
	for ch in s[::-1]:
		if ch == 'A':
			p += 1
		else:
			p -= 1
		if p < 0:
			print('No')
			break
	else:
		print('Yes')


for i in range(int(input())):
	n = int(input())
	li = input()
	pending = 0
	for m in li:
		if m == 'Q':
			pending += 1
		elif pending > 0:
			pending -= 1
	if pending == 0:
		print('Yes')
	else:
		print('No')


output = []

def calc():
	number = input()
	string = input()
	if string.endswith('Q'):
		output.append('No')
		return 0
	q = 0
	for x in string:
		if x == 'Q':
			q += 1
		elif x == 'A':
			q = max(q - 1, 0)
	if q > 0:
		output.append('No')
	else:
		output.append('Yes')
test_cases = int(input())
for i in range(test_cases):
	calc()
for i in output:
	print(i)


tst = int(input())
for i in range(tst):
	num = int(input())
	st = input()
	nQ = 0
	nA = 0
	for j in range(num):
		if st[j] == 'Q':
			nQ = nQ + 1
		else:
			nQ = nQ - 1
		if nQ < 0:
			nQ = 0
	if nQ == 0:
		print('Yes')
	else:
		print('No')


n = int(input())
temp = []
for i in range(n):
	questions = 0
	x = int(input())
	inp = input()
	for j in range(x):
		if inp[j] == 'Q':
			questions = questions + 1
		elif questions > 0:
			questions = questions - 1
	if questions == 0:
		temp.append('Yes')
	else:
		temp.append('No')
for k in range(n):
	print(temp[k])


import collections
import math
import sys
from queue import PriorityQueue

def main(testnumber):
	n = int(input())
	s = str(input())
	q = 0
	for i in range(len(s)):
		if s[i] == 'Q':
			q += 1
		else:
			q -= 1
		if q < 0:
			q = 0
	if q == 0:
		print('Yes')
	else:
		print('No')
t = int(input())
cnt = 1
while t > 0:
	main(cnt)
	cnt += 1
	t -= 1


def solve():
	l = int(input())
	s = input()
	q = 0
	for let in s:
		if let == 'Q':
			q += 1
		else:
			q = max(0, q - 1)
	if q:
		print('No')
	else:
		print('Yes')
t = int(input())
for i in range(t):
	solve()


def func():
	n = int(input())
	s = input()
	c = 0
	for i in s:
		if c < 0:
			c = 0
		if i == 'Q':
			c += 1
		if i == 'A':
			c -= 1
	if c > 0:
		print('No')
	else:
		print('Yes')
t = int(input())
for _ in range(t):
	func()


for jj in range(int(input())):
	n = int(input())
	s = input()
	q = 0
	for i in s:
		if i == 'Q':
			q += 1
		elif q > 0:
			q -= 1
	if q == 0:
		print('Yes')
	else:
		print('No')


from collections import deque
for i in range(int(input())):
	n = int(input())
	a = list(input())
	st = 0
	for i in a:
		if i == 'Q':
			st += 1
		elif i == 'A' and st > 0:
			st -= 1
	if st > 0:
		print('No')
	else:
		print('Yes')


tests = int(input())
for test in range(tests):
	n = int(input())
	order = input()
	stack = []
	for i in range(len(order)):
		if order[i] == 'Q':
			stack.append(i)
		elif order[i] == 'A' and stack:
			stack.pop()
	if stack == []:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	s = input()
	q = 0
	for c in s:
		if c == 'Q':
			q += 1
		else:
			q = max(0, q - 1)
	if q:
		print('No')
	else:
		print('Yes')


def solve(a, b):
	m = 0
	for i in b:
		if i == 'Q':
			m = m + 1
		else:
			m = max(m - 1, 0)
	if m < 1:
		return 'Yes'
	else:
		return 'No'
for _ in range(int(input())):
	a = int(input())
	b = input()
	print(solve(a, b))


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve():
	n = ni()
	s = list(INP())
	(a, q) = (0, 0)
	for i in range(n - 1, -1, -1):
		if s[i] == 'Q':
			a -= 1
			if a < 0:
				print('No')
				return
		else:
			a += 1
	print('Yes')
	return
t = ni()
for case in range(t):
	solve()


for _ in range(int(input())):
	l = int(input())
	s = input()
	nq = 0
	na = 0
	for i in s:
		if i == 'Q':
			nq += 1
		elif i == 'A':
			if nq > 0:
				nq -= 1
	if nq > 0:
		print('No')
	else:
		print('Yes')