Consider the infinite sequence s of positive integers, created by repeating the following steps:

  1. Find the lexicographically smallest triple of positive integers (a, b, c) such that 
    * a ⊕ b ⊕ c = 0, where ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 
    * a, b, c are not in s. 
Here triple of integers (a_1, b_1, c_1) is considered to be lexicographically smaller than triple (a_2, b_2, c_2) if sequence [a_1, b_1, c_1] is lexicographically smaller than sequence [a_2, b_2, c_2]. 
  2. Append a, b, c to s in this order. 
  3. 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 ≤ t ≤ 10^5) — the number of test cases.

Each of the next t lines contains a single integer n (1≤ n ≤ 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, ... 
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MX = 2e5 + 5;
const long long INF = 1e18;
const long double PI = acos((long double)-1);
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
int pct(int x) { return __builtin_popcount(x); }
int bit(int x) { return 31 - __builtin_clz(x); }
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
template <class A>
void re(complex<A>& c);
template <class A, class B>
void re(pair<A, B>& p);
template <class A>
void re(vector<A>& v);
template <class A, size_t SZ>
void re(array<A, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& d) {
  string t;
  re(t);
  d = stod(t);
}
void re(long double& d) {
  string t;
  re(t);
  d = stold(t);
}
template <class H, class... T>
void re(H& h, T&... t) {
  re(h);
  re(t...);
}
template <class A>
void re(complex<A>& c) {
  A a, b;
  re(a, b);
  c = {a, b};
}
template <class A, class B>
void re(pair<A, B>& p) {
  re(p.first, p.second);
}
template <class A>
void re(vector<A>& x) {
  for (auto& a : x) re(a);
}
template <class A, size_t SZ>
void re(array<A, SZ>& x) {
  for (auto& a : x) re(a);
}
template <class A, class B>
string to_string(pair<A, B> p);
template <class A>
string to_string(complex<A> c) {
  return to_string(make_pair(c.real(), c.imag()));
}
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(char c) {
  string second = "";
  second += c;
  return second;
}
string to_string(string second) { return second; }
string to_string(const char* second) { return (string)second; }
string to_string(vector<bool> v) {
  bool fst = 1;
  string res = "{";
  for (int i = (0); i < ((int)v.size()); ++i) {
    if (!fst) res += ", ";
    fst = 0;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t SZ>
string to_string(bitset<SZ> b) {
  string res = "";
  for (int i = (0); i < (SZ); ++i) res += char('0' + b[i]);
  return res;
}
template <class T>
string to_string(T v) {
  bool fst = 1;
  string res = "{";
  for (const auto& x : v) {
    if (!fst) res += ", ";
    fst = 0;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class A>
void pr(A x) {
  cout << to_string(x);
}
template <class H, class... T>
void pr(const H& h, const T&... t) {
  pr(h);
  pr(t...);
}
void ps() { pr("\n"); }
template <class H, class... T>
void ps(const H& h, const T&... t) {
  pr(h);
  if (sizeof...(t)) pr(" ");
  ps(t...);
}
void DBG() { cerr << "]" << endl; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << to_string(h);
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void unsyncIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
void setIO(string second = "") {
  unsyncIO();
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
using ul = uint64_t;
ul _nimProd[64][64];
ul nimProd(int i, int j) {
  ul& u = _nimProd[i][j];
  if (u) return u;
  if (!(i & j)) return u = 1ULL << (i | j);
  int a = (i & j) & -(i & j);
  return u = nimProd(i ^ a, j) ^
             nimProd((i ^ a) | (a - 1), (j ^ a) | (i & (a - 1)));
}
struct nb {
  ul x;
  nb() { x = 0; }
  nb(ul _x) : x(_x) {}
  explicit operator ul() { return x; }
  nb operator+(nb y) { return nb(x ^ y.x); }
  nb operator*(nb y) {
    ul res = 0;
    for (int i = (0); i < (64); ++i)
      if (x >> i & 1)
        for (int j = (0); j < (64); ++j)
          if (y.x >> j & 1) res ^= nimProd(i, j);
    return nb(res);
  }
  friend nb pow(nb b, ul p) {
    nb res = 1;
    for (; p; p /= 2, b = b * b)
      if (p & 1) res = res * b;
    return res;
  }
  friend nb inv(nb b) { return pow(b, -2); }
};
int t;
long long n;
void solve() {}
bool in(vector<int> a, int b) { return find(begin(a), end(a), b) != end(a); }
long long huh(long long a, int b) {
  if (b == 0) return a;
  if (b == 2) return huh(a, 1) ^ huh(a, 0);
  return (nb(2) * nb(a)).x;
}
long long get(long long a, int b) {
  for (int i = 0;; ++i) {
    long long p = 1LL << (2 * i);
    if (p >= a) return p * (b + 1) + huh(a - 1, b);
    a -= p;
  }
}
int main() {
  setIO();
  vector<int> seq;
  for (int z = (0); z < (100); ++z) {
    int cur = 1;
    while (in(seq, cur)) cur++;
    int CUR = cur + 1;
    while (in(seq, CUR) || in(seq, cur ^ CUR)) CUR++;
    seq.push_back(cur);
    seq.push_back(CUR);
    seq.push_back(cur ^ CUR);
    long long p = 1;
    while (p * 4 <= cur) p *= 4;
  }
  for (int a = (1); a < (101); ++a)
    for (int b = (0); b < (3); ++b) {
      assert(get(a, b) == seq[3 * (a - 1) + b]);
    }
  re(t);
  for (int i = (0); i < (t); ++i) {
    long long n;
    re(n);
    ps(get((n + 2) / 3, (n - 1) % 3));
  }
}
