Alice 和 Bob 正在玩游戏。他们有 $$$n$$$ 卡片,编号从 $$$1$$$ 到 $$$n$$$。游戏开始时,这些卡牌中的一部分交给Alice,其余的交给Bob。
编号为 $$$i$$$ 的牌击败编号为 $$$j$$$ 的牌当且仅当 $$$i \gt j$$$, ,但有一个例外:卡 $$$1$$$ 击败卡 $$$n$$$。
只要每个玩家至少拥有一张牌,游戏就会继续。在每个回合中,都会发生以下情况:
- Alice 选择她的一张牌并将其面朝上放在桌子上;
- 鲍勃看到爱丽丝的牌,选择了他的一张牌并将其面朝上放在桌子上;
- 如果 Alice 的牌击败了 Bob 的牌,则两张牌都被 Alice 拿走。否则,两张牌都会被鲍勃拿走。
玩家可以使用他们在前一个回合中获得的一张牌。
回合开始时没有牌的玩家输。如果两名玩家都发挥最佳,确定谁会获胜。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。
每个测试用例由两行组成:
- 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$) — 卡的数量;
- 第二行包含 $$$n$$$ 个字符,每个字符 A or B。如果第 $$$i$$$ 个字符是 A,则卡号 $$$i$$$ 最初被赋予给 Alice;否则,将其交给 Bob。
对输入的附加约束:在每个测试用例中,最初至少给 Alice 一张卡,最初给 Bob 至少一张卡。
输出
对于每个测试用例,输出 爱丽丝 如果 Alice 以最佳玩法获胜,或者 鲍勃 如果鲍勃获胜。可以证明,如果两个玩家都发挥最佳,游戏肯定会在有限的回合中以其中一个玩家获胜而结束。
示例
输入复制
82AB2BA4ABAB4BABA3BAA5AAAAB5BAAAB6BBBAAA
输出复制
Alice Bob Bob Bob Alice Alice Bob Alice
注意
在第一个测试用例中,Alice 只有一张卡,Bob 只有一张卡。由于爱丽丝的牌击败了鲍勃的牌,因此她在第一回合后获胜。
在第二个测试用例中,Alice 只有一张卡,Bob 只有一张卡。由于鲍勃的牌击败了爱丽丝的牌,因此他在第一回合后获胜。
在第三个测试用例中,有两种可能的游戏场景:
- 如果 Alice 在第一回合打出 $$$1$$$ 牌,Bob 可以用 $$$2$$$ 牌回应并拿走两张牌。然后,Alice 必须在第二回合打出 $$$3$$$ 牌,而 Bob 将通过打出 $$$4$$$ 牌来回应。然后,他赢了;
- 如果 Alice 在第一回合打出 $$$3$$$ 牌,Bob 可以用 $$$4$$$ 牌回应并拿走两张牌。然后,Alice 必须打出 $$$1$$$ 牌,而 Bob 可以用 $$$2$$$ 牌或 $$$3$$$ 牌来回应。然后,他赢了。
在第四个测试用例中,有两种可能的游戏场景:
- 如果 Alice 在第一回合打出 $$$2$$$ 牌,Bob 可以用 $$$3$$$ 牌回应并拿走两张牌。然后,爱丽丝必须在第二回合打出$$$4$$$ 牌,鲍勃将通过打出$$$1$$$ 牌来回应。然后,他赢了;
- 如果 Alice 在第一回合打出 $$$4$$$ 牌,Bob 可以用 $$$1$$$ 牌回应并拿走两张牌。然后,Alice 必须打出 $$$2$$$ 牌,而 Bob 可以用 $$$3$$$ 牌或 $$$4$$$ 牌来回应。然后,他赢了。