407013: GYM102680 H Last Robotics

Learning About Science and Technology Robotics is a program in which students build and program robots to compete in a task. The robots will compete on an assigned alliance, either on the Red Alliance or the Blue Alliance, with each alliance containing an infinite number of teams.

Because of the extreme skill curve this year, creating balanced alliances is of utmost importance. The team are already individually ranked from 1 to infinity based on how well each one's robot functions on its own. A string s is created to determine which teams will be on which alliance, given their overall ranking.

1. Create a string called $$$s$$$ and set it to "r"

2. Create a string called $$$t$$$ and set it to a copy of $$$s$$$.

3. Replace each character in $$$t$$$ with its opposite (replace "r" with "b" and "b" with "r")

4. Concatenate t to the end of $$$s$$$.

5. Repeat steps 2-4 indefinitely.

So after the first few iterations, $$$s$$$ will be:

r

rb

rbbr

rbbrbrrb

rbbrbrrbbrrbrbbr

rbbrbrrbbrrbrbbrbrrbrbbrrbbrbrrb

The characters in $$$s$$$ represent the alliance colors of the correspondingly ranked team. The 1st, 4th, and 7th ranked team will be Red, for example, and the 2nd, 3rd, and 8th ranked teams will be Blue. (Note that s is 1-indexed)

Because it would take a long time to read off which alliance an infinite number of teams would be on, LAST Robotics needs you to write a program to tell a team which alliance they will be on, given their ranking. Since matches are already 2 hours behind schedule, and teams up to the ranking of $$$10^{18}$$$ will ask you to which alliance they belong, your program must answer very large queries quickly.

The first line will contain an integer $$$T$$$, the number of teams that will ask you which alliance they will be on.

$$$T$$$ lines follow, each containing a single integer, $$$n$$$, the ranking of a given team (The best team is rank 1).

$$$1 \leq T \leq 200$$$

$$$1 \leq n \leq 10^{18}$$$

Output $$$T$$$ lines with each containing either "Red" or "Blue", representing the alliance of the team with the given ranking.

5
1
2
3
8
10000000000000000

Red
Blue
Blue
Blue
Blue

We must figure out the 1th, 2st, 3nd, 8th, and 10,000,000,000,000,000th index of s (1-based indexing) after a sufficient number of iterations in order to figure out the alliances of the appropriately ranked teams. Since $$$s$$$ will equal "rbbrbrrbrbbrbrrbrb...", the respective alliances are Red, Blue, Blue, Blue, and Blue.