완벽한 삼중항

양의 정수로 이루어진 무한 수열 $s$를 다음 단계를 반복하여 만든다.

1. 다음 조건을 만족하는 양의 정수 세 수 $(a, b, c)$ 중 사전순으로 가장 작은 것을 찾는다.

   • $a \oplus b \oplus c = 0$이다. 여기서 $\oplus$는 비트 단위 XOR 연산을 뜻한다.
   • $a$, $b$, $c$는 모두 $s$에 없다.

   세 수 $(a_1, b_1, c_1)$은 수열 $[a_1, b_1, c_1]$이 $[a_2, b_2, c_2]$보다 사전순으로 작을 때 $(a_2, b_2, c_2)$보다 작다.

2. $a$, $b$, $c$를 이 순서대로 $s$의 뒤에 붙인다.

3. 1번 단계로 돌아간다.

정수 $n$이 주어진다. $s$의 $n$번째 원소를 구하라.

이 문제는 $t$개의 독립적인 테스트 케이스에 답해야 한다.

수열 $a$가 수열 $b$보다 사전순으로 작다는 것은, 두 수열이 처음으로 달라지는 위치에서 $a$의 원소가 $b$의 대응하는 원소보다 작다는 뜻이다.

첫 번째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 10^5$)가 주어진다.

다음 $t$개의 줄에는 각각 정수 $n$ ($1 \le n \le 10^{16}$)이 하나씩 주어진다. 구하려는 원소의 위치이다.

각 테스트 케이스마다 답을 한 줄에 출력한다.

수열 $s$의 처음 원소는 $1, 2, 3, 4, 8, 12, 5, 10, 15, \dots$ 이다.