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".

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

中文：

您在一家大公司的技術支持質量控制部門工作。 您的工作是確保所有客戶問題均已得到解決。

今天，您需要檢查客戶和技術支持經理之間的對話副本。 根據工作規(guī)則，客戶的每條消息后面都必須有一條或多條消息，這是支持經理的答復。 然而，有時客戶提出問題的速度太快，以致于在客戶提出一些新問題后，經理對舊問題的一些回答才出現。

由于隱私政策的原因，您無法看到消息的全文，只能看到消息的順序以及每條消息的類型：客戶問題或技術支持經理的回復。 確保對話以客戶的問題開始。

您必須確定此對話框是否符合上述工作規(guī)則，否則肯定會違反規(guī)則。

輸入

每個測試包含多個測試用例。 第一行包含測試用例的數量 t (1≤t≤500)。 測試用例的描述如下。

每個測試用例的第一行包含一個整數 n (1≤n≤100) — 對話框中的消息總數。

每個測試用例的第二行由n個字符“Q”和“A”組成，按時間順序描述對話框中的消息類型。 字符“Q”表示包含客戶問題的消息，字符“A”表示包含技術支持經理答案的消息。 確保行中的第一個字符等于“Q”。

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

其實就是每個Q后面都有對應A即可，但是1個Q可能會有2個A對照，所以加一個變量去判斷即可；

下面是代碼：(很少用arraydeque,嘗試用一下)