题目描述

Alice 和 Bob 又来到了他们最喜欢的餐厅：Nim Sum Dim Sum。

他们坐在一张长桌的两侧，Alice 在左边，Bob 在右边。两人之间有 $N$ 个盘子，用字符串 $S_{1..N}$ 表示。每个盘子里装着以下两种食物之一：

• 杏仁豆腐，记为 'A'；
• BBQ 包子，记为 'B'。

Alice 只喜欢吃杏仁豆腐，Bob 只喜欢吃 BBQ 包子。他们轮流吃东西，规则如下：

• Alice 会选择任意一个装有杏仁豆腐的盘子，然后拉动很长的桌布，直到这个盘子来到她面前。在这个过程中，该盘子前面的前缀盘子都会摔到地上。之后 Alice 吃掉这个杏仁豆腐。
• Bob 接着会选择任意一个装有 BBQ 包子的盘子，然后拉动桌布，直到这个盘子来到桌子的右端。在这个过程中，该盘子后面的后缀盘子也会摔到地上。之后 Bob 吃掉这个包子。

上述过程不断重复，直到每个盘子要么被吃掉，要么被摔到地上。

如果轮到某个玩家行动时，桌上已经没有该玩家喜欢的食物，那么该玩家会跳过这一回合，什么也不做。

两位玩家唯一在意的是：谁能吃掉桌上最后一个剩余的盘子。双方都会基于这个目标选择要吃哪一个盘子。请判断最后一个盘子会被谁吃掉。

输入格式

输入第一行包含一个整数 $T$，表示测试用例数量。

对于每个测试用例：

• 第一行包含一个整数 $N$；
• 第二行包含字符串 $S$。

输出格式

对于第 $i$ 个测试用例，输出一行：

Case #i: winner

其中 winner 为：

• Alice，如果 Alice 吃掉最后一个盘子；
• Bob，如果 Bob 吃掉最后一个盘子。

数据范围

• $1\le T\le 95$
• $1\le N\le 600000$
• $S_{1..N}\in\{\texttt{A},\texttt{B}\}$

样例输入

6
7
ABBAAAB
1
A
1
B
2
AB
6
AAAAAA
7
BBBBBBA

样例输出

Case #1: Alice
Case #2: Alice
Case #3: Bob
Case #4: Bob
Case #5: Alice
Case #6: Alice

样例解释

在第一个测试用例中，桌面初始状态如下：

[Alice]ABBAAAB[Bob]

Alice 的一种获胜方式是：将桌布向自己方向拉动三格，使 ABB 三个盘子摔到地上，并吃掉第四个盘子中的杏仁豆腐，剩下：

[Alice]_AAB---[Bob]

Bob 此时只能把桌布拉回去，吃掉唯一剩下的包子，剩下：

[Alice]---_AA_[Bob]

Alice 接着拉动桌布，撞掉一个空盘位置，并吃掉第一个剩余的杏仁豆腐，剩下：

[Alice]_A_----[Bob]

桌上已经没有包子，所以 Bob 跳过这一回合：

[Alice]_A_----[Bob]

Alice 再次拉动桌布，撞掉一个空盘位置，吃掉唯一剩余的盘子，因此 Alice 获胜。

在第三个测试用例中，Alice 第一回合必须跳过，Bob 会吃掉唯一的包子并获胜。

在第四个测试用例中，Alice 第一回合必须吃掉第一个杏仁豆腐，然后 Bob 会在自己的第一回合吃掉剩下的包子并获胜。