L. Бесконечная пирамидка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваня решил построить бесконечную пирамидку из кубиков красного и синего цвета по особому правилу.

Ряды пирамидки нумеруются снизу вверх, начиная с единицы, а кубики в каждом ряду — слева направо, также начиная с единицы. В первом ряду (основании пирамидки) кубики идут группами чередующихся цветов: сначала идет один красный кубик, затем два синих, далее три красных, четыре синих, и так далее — $$$i$$$-я по счету группа состоит из $$$i$$$ кубиков одного цвета.

Каждый следующий ряд строится поверх предыдущего: для каждого $$$k \ge 1$$$ кубик в $$$n$$$-м ряду ($$$n \ge 2$$$) на $$$k$$$-й позиции ставится ровно посередине над кубиками на позициях $$$k$$$ и $$$k + 1$$$ из $$$(n - 1)$$$-го ряда. Цвет нового кубика выбирается по следующему правилу:

  • если два кубика под ним одного цвета, то на них ставится красный кубик;
  • если два кубика под ним разных цветов, то на них ставится синий кубик.

К сожалению, кубиков не хватило, чтобы достроить бесконечную пирамидку до конца, но Ване очень интересно, кубики каких цветов ему пришлось бы поставить в определенные позиции.

По заданным номерам ряда $$$n$$$ и позиции $$$k$$$ определите цвет соответствующего кубика для каждого запроса.

Входные данные

В первой строке дано целое число $$$q$$$ — количество запросов ($$$1 \le q \le 10^5$$$). В следующих $$$q$$$ строках даны по два числа $$$n$$$ и $$$k$$$ — ряд и номер позиции в ряду кубика, цвет которого нужно узнать ($$$1 \le n \le 10^5$$$; $$$1 \le k \le 10^{18}$$$).

Выходные данные

Для каждого запроса в отдельной строке выведите «R», если кубик на указанной позиции красный, и «B» в противном случае.

Пример
Входные данные
10
1 1
1 2
1 3
1 4
2 1
2 2
2 3
3 1
3 2
4 1
Выходные данные
R
B
B
R
B
R
B
B
B
R
Примечание

На рисунке изображен фрагмент пирамидки из десяти кубиков с основанием на первых четырех кубиках первого ряда:

В первом ряду ($$$n = 1$$$) сначала идет группа из одного красного кубика на позиции $$$1$$$, затем группа из двух синих кубиков на позициях $$$2$$$ и $$$3$$$, после чего начинается группа из трех красных кубиков (на рисунке показан ее первый кубик на позиции $$$4$$$).

Во втором ряду ($$$n = 2$$$):

  • кубик $$$(2, 1)$$$ стоит над кубиками $$$(1, 1)$$$ и $$$(1, 2)$$$ разных цветов, поэтому он синий («B»);
  • кубик $$$(2, 2)$$$ стоит над двумя синими кубиками $$$(1, 2)$$$ и $$$(1, 3)$$$, поэтому он красный («R»);
  • кубик $$$(2, 3)$$$ стоит над кубиками $$$(1, 3)$$$ и $$$(1, 4)$$$ разных цветов, поэтому он синий («B»).

Аналогично определяются цвета кубиков в рядах $$$n = 3$$$ и $$$4$$$.