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>
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
long long md = 1000000007;
using namespace std;
template <typename T>
T pw(T a, T b) {
  T c = 1, m = a;
  while (b) {
    if (b & 1) c = (c * m);
    m = (m * m), b /= 2;
  }
  return c;
}
template <typename T>
T ceel(T a, T b) {
  if (a % b == 0)
    return a / b;
  else
    return a / b + 1;
}
template <typename T>
T my_log(T n, T b) {
  T i = 1, ans = 0;
  while (1) {
    if (i > n) {
      ans--;
      break;
    }
    if (i == n) break;
    i *= b, ans++;
  }
  return ans;
}
template <typename T>
T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long pwmd(long long a, long long b) {
  long long c = 1, m = a;
  while (b) {
    if (b & 1) c = (c * m) % md;
    m = (m * m) % md;
    b /= 2;
  }
  return c;
}
long long modinv(long long n) { return pwmd(n, md - 2); }
long long inverse(long long i) {
  if (i == 1) return 1;
  return (md - ((md / i) * inverse(md % i)) % md + md) % md;
}
bool sortbysec(const pair<long long, long long> &a,
               const pair<long long, long long> &b) {
  return (a.second < b.second);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  long long t, n;
  cin >> t;
  while (t--) {
    cin >> n;
    if (n <= 4) {
      cout << n << "\n";
      continue;
    }
    long long q = 1;
    while (n >= 4ll * q) q *= 4ll;
    n -= (q - 1);
    long long e = n % 3, ans = 0;
    n /= 3;
    deque<long long> v;
    if (e == 0) {
      n--;
      long long o = n;
      if (n == 0) {
        cout << ((q + n) ^ (2ll * q + n)) << "\n";
        continue;
      }
      while (n > 0) {
        v.push_back(n & 1);
        n = (n >> 1ll);
      }
      reverse((v).begin(), (v).end());
      if (v.size() % 2) v.push_front(0);
      vector<long long> we(v.size());
      for (long long i = 1; i < v.size(); i++) {
        if (v[i] == 0 && v[i - 1] == 0) {
          we[i] = we[i - 1] = 0;
        } else if (v[i - 1] == 0 && v[i] == 1) {
          we[i - 1] = 1, we[i] = 0;
        } else if (v[i - 1] == 1 && v[i] == 0) {
          we[i] = we[i - 1] = 1;
        } else
          we[i] = 1, we[i - 1] = 0;
        i++;
      }
      ans = 0;
      reverse((we).begin(), (we).end());
      for (long long i = 0; i < we.size(); i++) {
        if (we[i]) ans += (1ll << i);
      }
      cout << ((q + o) ^ (2ll * q + ans)) << "\n";
    } else if (e == 1)
      cout << (q + n) << "\n";
    else {
      if (n == 0) {
        cout << (2ll * q + n) << "\n";
        continue;
      }
      while (n > 0) {
        v.push_back(n & 1);
        n = (n >> 1ll);
      }
      reverse((v).begin(), (v).end());
      if (v.size() % 2) v.push_front(0);
      vector<long long> w(v.size());
      for (long long i = 1; i < v.size(); i += 2) {
        if (v[i] == 0 && v[i - 1] == 0) {
          w[i] = w[i - 1] = 0;
        } else if (v[i - 1] == 0 && v[i] == 1) {
          w[i] = 0, w[i - 1] = 1;
        } else if (v[i - 1] == 1 && v[i] == 0) {
          w[i] = w[i - 1] = 1;
        } else
          w[i] = 1, w[i - 1] = 0;
      }
      reverse((w).begin(), (w).end());
      for (long long i = 0; i < w.size(); i++) {
        if (w[i]) ans += (1ll << i);
      }
      cerr << "ans"
           << " = " << ans << endl;
      ;
      cerr << "w[0]"
           << " = " << w[0] << endl;
      ;
      cerr << "w[1]"
           << " = " << w[1] << endl;
      ;
      cout << (2ll * q + ans) << "\n";
    }
  }
}
