题目描述

Alice 和 Bob 正在玩一款游戏。他们共有 $n$ 张卡片，编号从 $1$ 到 $n$ 。游戏开始时，一些卡片分配给了 Alice，剩下的卡片分配给了 Bob。

卡片 $i$ 能打败卡片 $j$ 当且仅当 $i > j$ ，唯一的例外是卡片 $1$ 可以打败卡片 $n$ 。

游戏进行的规则如下（当两人手中都有卡片时）：

1 Alice 选择一张自己的卡片，正面朝上放在桌上；

2 Bob 看到 Alice 的卡后，选择一张自己的卡，也正面朝上放在桌上；

3 如果 Alice 的卡能打败 Bob 的卡，那么两张卡都归 Alice 所有，否则两张卡都归 Bob 所有。

两人可以在之后的回合中使用自己获得的卡牌。

当某一方在其轮到操作时没有任何卡牌可以打出时，游戏结束，该玩家失败。

已知双方都采取最优策略，判断最终谁会赢。

输入格式

第一行：一个整数 $t$ ，表示测试组数。（ $1 \le t \le 5000$ ）

接下来 $t$ 个测试用例，每个包含两行：

第一行：一个整数 $n$ （ $2 \le n \le 50$ ）— 卡片数量；

第二行：一个长度为 $n$ 的字符串，仅包含 A 和 B。如果第 $i$ 个字符是 A，表示卡片 $i$ 初始属于 Alice，否则属于 Bob。

保证每组数据中，Alice 和 Bob 都至少有一张卡。

每组测试用例输出一行，输出 Alice 或 Bob，表示最终的胜者。

8
2
AB
2
BA
4
ABAB
4
BABA
3
BAA
5
AAAAB
5
BAAAB
6
BBBAAA

Alice
Bob
Bob
Bob
Alice
Alice
Bob
Alice

注

在第一个测试案例中，爱丽丝只有一张牌，而鲍勃只有一张牌。由于爱丽丝的牌战胜了鲍勃的牌，所以她在第一轮后获胜。

在第二个测试案例中，爱丽丝只有一张牌，而鲍勃只有一张牌。由于鲍勃的牌赢了爱丽丝的牌，所以他在第一轮后获胜。

在第三个测试案例中，有两种可能的游戏情况：

如果爱丽丝在第一轮出了 $1$ 这张牌，那么鲍勃可以用 $2$ 这张牌回应，并拿走两张牌。然后，爱丽丝必须在第二轮出牌 $3$ ，而鲍勃将以出牌 $4$ 作为回应。然后，他就赢了；
如果爱丽丝在第一轮出牌 $3$ ，鲍勃可以回应出牌 $4$ 并拿走两张牌。然后，爱丽丝必须出牌 $1$ ，而鲍勃可以出牌 $2$ 或 $3$ 。然后，他就赢了。

在第四个测试案例中，有两种可能的游戏情况：

如果爱丽丝在第一轮出牌 $2$ ，鲍勃可以回应出牌 $3$ 并拿走两张牌。然后，爱丽丝必须在第二轮出牌 $4$ ，而鲍勃将以出牌 $1$ 作为回应。然后，他就赢了；
如果爱丽丝在第一轮出牌 $4$ ，鲍勃可以回应出牌 $1$ 并拿走两张牌。然后，爱丽丝必须出牌 $2$ ，而鲍勃可以回应 $3$ 或 $4$ 。然后，他就赢了。