CF1704F.Colouring Game

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.

爱丽丝和鲍勃正在玩一个游戏。一行中有 $n$ 个格子，每个格子初始时为红色或蓝色。爱丽丝先手。

每一轮中，爱丽丝选择两个相邻的格子，要求其中至少有一个是红色格子，然后将这两个格子都涂成白色；接着鲍勃选择两个相邻的格子，要求其中至少有一个是蓝色格子，然后将这两个格子都涂成白色。无法进行操作的玩家输掉游戏。

假设爱丽丝和鲍勃均采取最优策略，判断谁获胜。

注意：被选中的格子可以是白色，只要另一个格子满足相应约束条件即可。

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$.

第一行包含一个整数 $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$。

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

对于每个测试用例，在单独一行输出获胜者的名字。

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.

在讲义中，单元格编号从左到右递增。

在 Alice 的第一个测试用例中，她有两种选择：涂染第一和第二个单元格，或涂染第二和第三个单元格。无论 Alice 选择哪一种，她的操作结束后都恰好有一个蓝色单元格。Bob 只需将该蓝色单元格及其相邻单元格涂染，所有单元格都将变为白色，Alice 将无法继续操作。因此 Bob 获胜。

在第二个测试用例中，无论 Alice 如何选择，Bob 都能在 $2$ 回合内涂染第四和第五个单元格。

在第三个测试用例中，首先 Alice 涂染第三和第四个单元格。无论 Bob 选择涂染第一和第二个单元格，还是第五和第六个单元格，Alice 都可以接着涂染剩余的两个单元格。

在第四个测试用例中，首先 Alice 涂染第二和第三个单元格。若 Bob 涂染第五和第六个单元格，或第四和第五个单元格，则 Alice 涂染第七和第八个单元格；若 Bob 涂染第七和第八个单元格，则 Alice 涂染第五和第六个单元格。

在第五个测试用例中，Alice 首先选择中间两个单元格；此时 Bob 显然仅有两种选择，无论他选哪一种，Alice 都可选择另一种而获胜。

在第八个测试用例中，无论 Alice 如何选择，Bob 都可选择另外两个对称位置的单元格。