题目描述

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$）——测试用例的数量。

每个测试用例包含两行：

• 第一行包含一个整数 $n$（$2 \le n \le 50$）——卡牌的数量；
• 第二行包含 $n$ 个字符，每个字符是 A 或 B。如果第 $i$ 个字符是 A，则编号 $i$ 的卡牌初始属于 Alice；否则属于 Bob。

输入数据的额外约束：每个测试用例中，Alice 和 Bob 初始至少各有一张卡牌。

输出格式

对于每个测试用例，如果 Alice 在最优策略下获胜，输出 Alice；否则输出 Bob。可以证明在双方都采取最优策略时，游戏一定会在有限回合内结束，且一方必定获胜。

说明/提示

在第一个测试用例中，Alice 和 Bob 各有一张卡牌。由于 Alice 的卡牌能击败 Bob 的卡牌，她在第一回合后获胜。

在第二个测试用例中，Alice 和 Bob 各有一张卡牌。由于 Bob 的卡牌能击败 Alice 的卡牌，他在第一回合后获胜。

在第三个测试用例中，有两种可能的游戏进程：

• 如果 Alice 在第一回合出卡 $1$，Bob 可以用卡 $2$ 应对并收走两张卡。然后 Alice 必须在第二回合出卡 $3$，Bob 会用卡 $4$ 应对，最终 Bob 获胜；
• 如果 Alice 在第一回合出卡 $3$，Bob 可以用卡 $4$ 应对并收走两张卡。然后 Alice 必须出卡 $1$，Bob 可以用卡 $2$ 或卡 $3$ 应对，最终 Bob 获胜。

在第四个测试用例中，有两种可能的游戏进程：

• 如果 Alice 在第一回合出卡 $2$，Bob 可以用卡 $3$ 应对并收走两张卡。然后 Alice 必须在第二回合出卡 $4$，Bob 会用卡 $1$ 应对，最终 Bob 获胜；
• 如果 Alice 在第一回合出卡 $4$，Bob 可以用卡 $1$ 应对并收走两张卡。然后 Alice 必须出卡 $2$，Bob 可以用卡 $3$ 或卡 $4$ 应对，最终 Bob 获胜。

翻译由 DeepSeek V3 完成

样例

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