Colouring Game

题意翻译

Alice 和 Bob 在玩游戏。有 $n$ 个格子排成一行，每个格子被涂成了红色或蓝色。 Alice 每次操作选择两个相邻的格子，要求其中至少有一个是红色，然后把这两个格子涂成白色。 Bob 每次操作选择两个相邻的格子，要求其中至少有一个是蓝色，然后把这两个格子涂成白色。 他们轮流进行操作（Alice 先手），不能操作的人就输了。 现在给定初始局面，请问在他们都足够聪明的前提下，谁会获得胜利？

题目描述

Alice and Bob are playing a game. There are $ n $ cells in a row. Initially each cell is either red or blue. Alice goes first. On each turn, Alice chooses two neighbouring cells which contain at least one red cell, and paints that two cells white. Then, Bob chooses two neighbouring cells which contain at least one blue cell, and paints that two cells white. The player who cannot make a move loses. Find the winner if both Alice and Bob play optimally. Note that a chosen cell can be white, as long as the other cell satisfies the constraints.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. Description of test cases follows. For each test case, the first line contains an integer $ n $ ( $ 2 \leq n \leq 5 \cdot 10^5 $ ) — the number of cells. The second line contains a string $ s $ of length $ n $ — the initial state of the cells. The $ i $ -th cell is red if $ s_i = $ R, blue if $ s_i = $ B. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

输出格式

For each test case, output the name of the winner on a separate line.

输入输出样例

输入样例 #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

说明

In the notes, the cell numbers increase from left to right. In the first testcase for Alice, she has two choices: paint the first and the second cells, or paint the second and the third cells. No matter what choice Alice makes, there will be exactly one blue cell after Alice's move. Bob just needs to paint the blue cell and its neighbour, then every cell will be white and Alice can't make a move. So Bob is the winner. In the second testcase no matter what Alice chooses, Bob can choose to paint the fourth and fifth cells in $ 2 $ turns. In the third testcase at first, Alice paints the third and the fourth cells. It doesn't matter if Bob paints the first and the second cells or the fifth and sixth cells, as Alice can paint the other two cells. In the fourth testcase at first, Alice paints the second and the third cells. If Bob paints the fifth and the sixth cells or the fourth and the fifth cells, then Alice paints the seventh and the eighth cells. If Bob paints the seventh and the eighth cells, then Alice paints the fifth and the sixth cells. In the fifth Alice chooses the middle two cells at first, then Bob obviously has only two options, whichever variant he chooses, Alice can choose the other one and win. In the eighth no matter what Alice chooses, Bob can choose the other two symmetrical cells.

**题目大意：**
爱丽丝和鲍勃在玩一个游戏。有一行共 $ n $ 个格子，初始时每个格子要么是红色，要么是蓝色。爱丽丝先手，每次操作选择两个相邻的格子，其中至少有一个是红色，并将这两个格子涂成白色。然后鲍勃操作，他选择两个相邻的格子，其中至少有一个是蓝色，也将这两个格子涂成白色。不能操作的人就输了。给定初始局面，请问在两人都足够聪明的情况下，谁会获胜？

**输入输出格式：**
**输入格式：**
第一行包含一个整数 $ 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 $。

**输出格式：**
对于每个测试用例，输出一个单独的行，包含获胜者的名字。**题目大意：** 爱丽丝和鲍勃在玩一个游戏。有一行共 $ n $ 个格子，初始时每个格子要么是红色，要么是蓝色。爱丽丝先手，每次操作选择两个相邻的格子，其中至少有一个是红色，并将这两个格子涂成白色。然后鲍勃操作，他选择两个相邻的格子，其中至少有一个是蓝色，也将这两个格子涂成白色。不能操作的人就输了。给定初始局面，请问在两人都足够聪明的情况下，谁会获胜？ **输入输出格式：** **输入格式：** 第一行包含一个整数 $ 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 $。 **输出格式：** 对于每个测试用例，输出一个单独的行，包含获胜者的名字。