Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Perfect Triples

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputConsider the infinite sequence $$$s$$$ of positive integers, created by repeating the following steps:

- Find the lexicographically smallest triple of positive integers $$$(a, b, c)$$$ such that
- $$$a \oplus b \oplus c = 0$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.
- $$$a$$$, $$$b$$$, $$$c$$$ are not in $$$s$$$.

- Append $$$a$$$, $$$b$$$, $$$c$$$ to $$$s$$$ in this order.
- Go back to the first step.

You have integer $$$n$$$. Find the $$$n$$$-th element of $$$s$$$.

You have to answer $$$t$$$ independent test cases.

A sequence $$$a$$$ is lexicographically smaller than a sequence $$$b$$$ if in the first position where $$$a$$$ and $$$b$$$ differ, the sequence $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

Each of the next $$$t$$$ lines contains a single integer $$$n$$$ ($$$1\le n \le 10^{16}$$$) — the position of the element you want to know.

Output

In each of the $$$t$$$ lines, output the answer to the corresponding test case.

Example

Input

9 1 2 3 4 5 6 7 8 9

Output

1 2 3 4 8 12 5 10 15

Note

The first elements of $$$s$$$ are $$$1, 2, 3, 4, 8, 12, 5, 10, 15, \dots $$$

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/04/2020 00:02:04 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|