← 返回题目列表

Codeforces · 1287/A

A. 愤怒的学生

中文机器翻译题面 查看原题

今天是 SIS.Winter 的步行游览日,因此 $$$t$$$ 组学生正在参观托尔若克。托尔若克的街道非常狭窄,学生们不得不排成一排。

起初,一些学生很生气。让我们用一串大写字母“A”和“P”来描述一组学生:

- “A”对应愤怒的学生
- “P”对应一个有耐心的学生

这样的字符串描述了从最后一个学生到第一个学生的行。

每分钟,每个愤怒的学生都会向下一个学生扔雪球。正式地,如果一个愤怒的学生对应于描述一个组的字符串中索引为 $$$i$$$ 的字符,那么他们将向对应于索引为 $$$i+1$$$ 的字符对应的学生扔一个雪球(学生从最后一个学生到第一个学生)。如果目标学生还没有生气,他们就会生气。即使第一个(字符串中最右边的)学生很生气,他们也不会扔雪球,因为他们前面没有人。

让我们看一下第一个示例测试。该行最初看起来像这样:PPAP。然后,一分钟后,唯一一个愤怒的学生会向他们面前的学生扔一个雪球,他们也生气了:PPAA。从此以后,再也没有学生生气了。

你的任务是帮助 SIS.Winter 老师确定学生对每个小组生气的最后时刻。

输入

第一行包含一个整数 $$$t$$$ — 学生组的数量 ($$$1 \le t \le 100$$$)。以下 $$$2t$$$ 行包含学生组的描述。

小组的描述以整数 $$$k_i$$$ ($$$1 \le k_i \le 100$$$) 开头——该小组中的学生人数,后跟字符串 $$$s_i$$$,由 $$$k_i$$$ 字母“A”和“P”组成,描述第 $$$i$$$ 组学生。

输出

对于每个组输出单个整数 - 学生生气的最后一刻。

示例

输入 #1

1
4
PPAP

输出 #1

1

输入 #2

3
12
APPAPPPAPPPP
3
AAP
3
PPA

输出 #2

4
1
0

注意

在第一次测试中,$$$1$$$ 分钟后,学生的状态变为 PPAA。此后,不会出现新的愤怒学生。

在第二个tets中,第一组学生的状态是:

- $$$1$$$ 分钟后 — AAPAAPPAAPPP
- $$$2$$$ 分钟后 — AAAAAPAAAPP
- $$$3$$$ 分钟后 — AAAAAAAAAAAP
- $$$4$$$ 分钟后,所有 $$$12$$$ 学生都生气了

在 $$$1$$$ 分钟后的第二组中,所有学生都很生气。