说明

有一排 $N$ 个石子，每个石子被涂成白色或黑色。

Alice 和 Bob 使用这些石子玩一个游戏，规则如下：

• 两位玩家轮流行动，Alice 先手。
• 在每个回合中，当前玩家必须从石子的最左端或最右端恰好移除一个石子。
• 如果两位玩家移除的黑色石子的总数达到 $M$，则执行该移动的玩家输掉游戏，另一名玩家获胜。

假设双方都采取最优策略，请判断哪位玩家会赢得游戏。题目保证黑色石子的数量至少为 $M$。

输入格式

输入包含多个测试用例。

第一行包含一个整数 $T$（$1 \leq T \leq 1000$），表示测试用例的数量。

接下来是 $T$ 个测试用例。每个测试用例的格式如下。

对于每个测试用例，第一行包含两个整数 $N$（$1 \leq N \leq 500\,000$）和 $M$（$1 \leq M \leq N$），分别表示石子的总数和导致失败的阈值。

第二行包含一个长度为 $N$ 的字符串 $S$，仅由字符 'B' 和 'W' 组成。$S$ 的第 $i$ 个字符表示从左数第 $i$ 个石子的颜色：如果石子是黑色，则为 'B'；如果是白色，则为 'W'。题目保证黑色石子的数量至少为 $M$。

保证所有测试用例的 $N$ 的总和不超过 $500\,000$。

输出格式

对于 $T$ 个测试用例，逐行输出答案。对于每个测试用例，输出将会获胜的玩家的名字。

3
5 1
WBBWB
5 2
WBBWB
5 3
WBBWB

Alice
Alice
Bob

提示

在第一个测试用例中，如果 Alice 移除最左边的白色石子，剩下的石子序列为 “BBWB”。无论 Bob 从哪一端选择，他最终都会拿到一个黑色石子，因此 Bob 输掉游戏。

在第二个测试用例中，Alice 会获胜。例如，游戏可能按以下步骤进行：

1. Alice 移除最右边的黑色石子。
2. Bob 移除最右边的白色石子。
3. Alice 移除最左边的白色石子。
4. Bob 移除最右边的黑色石子。

翻译由 DeepSeek V3.2 完成