Alice 和 Bob 正在玩游戏。一行中有 $$$n$$$ 个单元格。最初,每个单元格要么是红色,要么是蓝色。爱丽丝先走。
在每一回合中,Alice 选择两个包含至少一个红色单元格的相邻单元格,并将这两个单元格涂成白色。然后,Bob 选择两个包含至少一个蓝色单元格的相邻单元格,并将这两个单元格涂成白色。无法采取行动的玩家就输了。
如果 Alice 和 Bob 都表现最佳,则找到获胜者。
请注意,只要其他单元格满足约束条件,所选单元格就可以是白色。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) — 单元格数量。
第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$ — 单元格的初始状态。如果 $$$s_i = $$$ R,则第 $$$i$$$ 个单元格为红色;如果 $$$s_i = $$$ B,则为蓝色。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,在单独的行中输出获胜者的姓名。
示例
输入 #1
8 3 BRB 5 RRBBB 6 RBRBRB 8 BBRRBRRB 6 BRRBRB 12 RBRBRBRBRRBB 12 RBRBRBRBBBRR 4 RBBR
输出 #1
Bob Bob Alice Alice Alice Alice Bob Bob
注意
在注释中,单元格编号从左到右增加。
在 Alice 的第一个测试用例中,她有两个选择:绘制第一个和第二个单元格,或者绘制第二个和第三个单元格。无论Alice做出什么选择,Alice移动后都会有一个蓝色单元格。鲍勃只需要把蓝色的格子和它的邻居涂上颜色,然后每个格子都会变成白色,爱丽丝就不能移动了。所以鲍勃是赢家。
在第二个测试用例中,无论 Alice 选择什么,Bob 都可以选择以 $$$2$$$ 轮流绘制第四个和第五个单元格。
首先在第三个测试用例中,Alice 绘制了第三个和第四个单元格。 Bob 绘制第一个和第二个单元格还是第五个和第六个单元格并不重要,因为 Alice 可以绘制其他两个单元格。
首先,在第四个测试用例中,Alice 绘制了第二个和第三个单元格。如果鲍勃绘制第五和第六个单元格或第四和第五个单元格,那么爱丽丝绘制第七和第八个单元格。如果鲍勃绘制第七个和第八个单元格,那么爱丽丝绘制第五个和第六个单元格。
在第五个中,Alice首先选择了中间的两个单元格,那么Bob显然只有两个选择,无论他选择哪个变体,Alice都可以选择另一个并获胜。
在第八个中,无论Alice选择什么,Bob都可以选择另外两个对称的单元格。