题目描述

在 SIS.Winter 的步行游览日，有 $t$ 个学生小组正在参观 Torzhok。Torzhok 的街道非常狭窄，学生们只能一个接一个地排成一行。

最初，有些学生是生气的。我们用由大写字母 "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$）开始，表示该小组的学生人数，接着是一行长度为 $k_i$ 的字符串 $s_i$，由字母 "A" 和 "P" 组成，描述第 $i$ 个小组的学生队列。

输出格式

对于每个小组，输出一个整数，表示最后一个学生变得生气的时刻。

说明/提示

在第一个测试中，经过 $1$ 分钟后，学生的状态变为 PPAA。之后不会有新的学生变得生气。

在第二个测试中，第一个小组的状态变化如下：

• 经过 $1$ 分钟：AAPAAPPAAPPP
• 经过 $2$ 分钟：AAAAAAPAAAPP
• 经过 $3$ 分钟：AAAAAAAAAAAP
• 经过 $4$ 分钟后，所有 $12$ 名学生都变得生气

在第二个小组中，经过 $1$ 分钟后，所有学生都变得生气。

由 ChatGPT 4.1 翻译

样例

1
4
PPAP

1

3
12
APPAPPPAPPPP
3
AAP
3
PPA

4
1
0