CF 1754A - Technical Support

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≤t≤500). Description of the test cases follows.

The first line of each test case contains one integer n (1≤n≤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".

----------------------------------------------------------------------

中文：

您在一家大公司的技术支持质量控制部门工作。 您的工作是确保所有客户问题均已得到解决。

今天，您需要检查客户和技术支持经理之间的对话副本。 根据工作规则，客户的每条消息后面都必须有一条或多条消息，这是支持经理的答复。 然而，有时客户提出问题的速度太快，以致于在客户提出一些新问题后，经理对旧问题的一些回答才出现。

由于隐私政策的原因，您无法看到消息的全文，只能看到消息的顺序以及每条消息的类型：客户问题或技术支持经理的回复。 确保对话以客户的问题开始。

您必须确定此对话框是否符合上述工作规则，否则肯定会违反规则。

输入

每个测试包含多个测试用例。 第一行包含测试用例的数量 t (1≤t≤500)。 测试用例的描述如下。

每个测试用例的第一行包含一个整数 n (1≤n≤100) — 对话框中的消息总数。

每个测试用例的第二行由n个字符“Q”和“A”组成，按时间顺序描述对话框中的消息类型。 字符“Q”表示包含客户问题的消息，字符“A”表示包含技术支持经理答案的消息。 确保行中的第一个字符等于“Q”。

--------------------------------------------------

其实就是每个Q后面都有对应A即可，但是1个Q可能会有2个A对照，所以加一个变量去判断即可；

下面是代码：(很少用arraydeque,尝试用一下)