[Solution] Colouring Game Codeforces Solution

F. Colouring Game

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Alice and Bob are playing a game. There are n$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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 other cell satisfies the constraints.

Input

The first line contains a single integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases. Description of test cases follows.

For each test case, the first line contains an integer n$n$ (2≤n≤5⋅105$2\le n\le 5\cdot {10}^5$) — the number of cells.

The second line contains a string s$s$ of length n$n$ — the initial state of the cells. The i$i$-th cell is red if si=$s_i=$ R, blue if si=$s_i=$ B.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 5⋅105$5\cdot {10}^5$.

Output

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