CF1287A.Angry Students

It's a walking tour day in SIS.Winter, so $t$ groups of students are visiting Torzhok. Streets of Torzhok are so narrow that students have to go in a row one after another.

Initially, some students are angry. Let's describe a group of students by a string of capital letters "A" and "P":

• "A" corresponds to an angry student
• "P" corresponds to a patient student

Such string describes the row from the last to the first student.

Every minute every angry student throws a snowball at the next student. Formally, if an angry student corresponds to the character with index $i$ in the string describing a group then they will throw a snowball at the student that corresponds to the character with index $i+1$ (students are given from the last to the first student). If the target student was not angry yet, they become angry. Even if the first (the rightmost in the string) student is angry, they don't throw a snowball since there is no one in front of them.

Let's look at the first example test. The row initially looks like this: PPAP. Then, after a minute the only single angry student will throw a snowball at the student in front of them, and they also become angry: PPAA. After that, no more students will become angry.

Your task is to help SIS.Winter teachers to determine the last moment a student becomes angry for every group.

今天是 SIS.Winter 的步行游览日，因此共有 $t$ 组学生正在参观托尔若克（Torzhok）。托尔若克的街道十分狭窄，学生们只能排成一列依次行进。

初始时，部分学生处于愤怒状态。我们用一个仅由大写字母 "A" 和 "P" 构成的字符串来描述一组学生：

• "A" 表示一名愤怒的学生；
• "P" 表示一名耐心的学生。

该字符串从队尾（最后一名学生）到队首（第一名学生）进行描述。

每一分钟，每一名愤怒的学生都会向其前方的一名学生投掷一个雪球。形式化地讲：若某愤怒学生在描述该组学生的字符串中对应下标为 $i$ 的字符，则他将向对应下标为 $i+1$ 的字符所代表的学生投掷雪球（注意：字符串中学生顺序是从队尾到队首）。若被击中的学生此前尚未愤怒，则他们将变为愤怒状态。即使最前方（即字符串中最右侧）的学生是愤怒的，他们也不会投掷雪球，因为其前方已无其他学生。

我们来看第一个样例测试。初始队列为：PPAP。一分钟后，唯一一名愤怒的学生将向其前方的学生投掷雪球，后者随之变为愤怒：PPAA。此后，将不再有新的学生变为愤怒。

你的任务是帮助 SIS.Winter 的教师们，对每一组学生，确定最后一名学生变为愤怒的时刻。

The first line contains a single integer $t$ — the number of groups of students ($1 \le t \le 100$). The following $2t$ lines contain descriptions of groups of students.

The description of the group starts with an integer $k_i$ ($1 \le k_i \le 100$) — the number of students in the group, followed by a string $s_i$, consisting of $k_i$ letters "A" and "P", which describes the $i$-th group of students.

第一行包含一个整数 $t$ —— 学生组的数量（$1 \le t \le 100$）。接下来的 $2t$ 行包含各学生组的描述。

每组学生的描述以一个整数 $k_i$（$1 \le k_i \le 100$）开始，表示该组的学生人数；随后是一个长度为 $k_i$ 的字符串 $s_i$，其仅由字母 "A" 和 "P" 组成，用于描述第 $i$ 组学生。

For every group output single integer — the last moment a student becomes angry.

对每组数据输出一个整数——学生变得愤怒的最后时刻。

In the first test, after $1$ minute the state of students becomes PPAA. After that, no new angry students will appear.

In the second tets, state of students in the first group is:

• after $1$ minute — AAPAAPPAAPPP
• after $2$ minutes — AAAAAAPAAAPP
• after $3$ minutes — AAAAAAAAAAAP
• after $4$ minutes all $12$ students are angry

In the second group after $1$ minute, all students are angry.

在第一次测试中，1 分钟后学生的状态变为 PPAA。此后将不再有新的愤怒学生出现。

在第二次测试中，第一组学生的状态为：

• 1 分钟后 — AAPAAPPAAPPP
• 2 分钟后 — AAAAAAPAAAPP
• 3 分钟后 — AAAAAAAAAAAP
• 4 分钟后，全部 12 名学生均变为愤怒状态

第二组学生在 1 分钟后，所有学生均已变为愤怒状态。