Рассмотрим бесконечную последовательность $$$s$$$ натуральных чисел, построенную повторением следующих шагов:

1. Найдите лексикографически наименьшую тройку натуральных чисел $$$(a, b, c)$$$ такую, ​​что
   • $$$a \oplus b \oplus c = 0$$$, где $$$\oplus$$$ обозначает побитовое исключающее ИЛИ.
   • $$$a$$$, $$$b$$$, $$$c$$$ не находятся в $$$s$$$.
   Здесь тройка целых чисел $$$(a_1, b_1, c_1)$$$ считается лексикографически меньше тройки $$$(a_2, b_2, c_2)$$$, если последовательность $$$[a_1, b_1, c_1]$$$ лексикографически меньше последовательности $$$[a_2, b_2, c_2]$$$
2. Добавьте $$$a$$$, $$$b$$$, $$$c$$$ в конец $$$s$$$ в этом порядке.
3. Вернитесь к первому шагу.

У вас есть целое число $$$n$$$. Найдите $$$n$$$-й элемент $$$s$$$.

Вы должны ответить на $$$t$$$ независимых тестовых случаев.

Последовательность $$$a$$$ лексикографически меньше последовательности $$$b$$$, если в первой позиции, где $$$a$$$ и $$$b$$$ различны, в последовательности $$$a$$$ элемент меньше, чем соответствующий элемент в $$$b$$$.