#P1338C. Perfect Triples
Perfect Triples
Description
Consider the infinite sequence of positive integers, created by repeating the following steps:
- Find the lexicographically smallest triple of positive integers such that
- , where denotes the bitwise XOR operation.
- , , are not in .
- Append , , to in this order.
- Go back to the first step.
You have integer . Find the -th element of .
You have to answer independent test cases.
A sequence is lexicographically smaller than a sequence if in the first position where and differ, the sequence has a smaller element than the corresponding element in .
The first line contains a single integer () — the number of test cases.
Each of the next lines contains a single integer () — the position of the element you want to know.
In each of the lines, output the answer to the corresponding test case.
Input
The first line contains a single integer () — the number of test cases.
Each of the next lines contains a single integer () — the position of the element you want to know.
Output
In each of the lines, output the answer to the corresponding test case.
Note
The first elements of are