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, ... 
import java.io.*;
import java.util.*;

public class C {
  PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  StringTokenizer tok;
  long[] firsts = { 1, 2, 3, 4, 8, 12, 5, 10, 15, 6, 11, 13, 7, 9, 14 };
  long[] oneOrder = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
  long[] twoOrder = { 0, 2, 3, 1, 8, 10, 11, 9, 12, 14, 15, 13, 4, 6, 7, 5 };
  long[] threeOrder = { 0, 3, 1, 2, 12, 15, 13, 14, 4, 7, 5, 6, 8, 11, 9, 10 };
  HashMap<Long, Long> memo = new HashMap<>();

  public void go() throws IOException {
    // checker();
    StringTokenizer tok = new StringTokenizer(in.readLine());
    int zzz = Integer.parseInt(tok.nextToken());
    for (int zz = 0; zz < zzz; zz++) {
      ntok();
      long n = lpar();
      out.println(getVal(n));
    }

    out.flush();
    in.close();
  }

  public void checker() {
    boolean[] seen = new boolean[1000000];
    ArrayList<Integer> list = new ArrayList<>();
    int n = 100000;
    for (int i = 0; i < n; i++) {
      int a = 1;
      while (seen[a]) {
        a++;
      }
      seen[a] = true;
      int b = 1;
      while (seen[b] || seen[a ^ b]) {
        b++;
      }
      seen[b] = true;
      int c = a ^ b;
      seen[c] = true;
      list.add(a);
      list.add(b);
      list.add(c);
      // System.out.printf("%d %d %d%n", a, b, c);
      // System.out.printf("%d %d %d%n", a & 0b1111, b & 0b1111, c & 0b1111);
      // System.out.printf("%d %d %d%n", a & 0b111111, b & 0b111111, c & 0b111111);
      // System.out.printf("%d %d %d%n", a & 0b11111110000, b & 0b11111110000, c &
      // 0b11111110000);
      // System.out.printf("%d %d %d%n", a >> 4, b >> 4, c >> 4);
    }
    // System.out.println(list);
    for (int i = 0; i < n * 3; i++) {
      // System.out.printf("n=%d: %d %d%n", i + 1, list.get(i), getVal(i + 1));
      if (list.get(i) != getVal(i + 1)) {
        System.out.println("WRONG");
        System.out.println(i);
        break;
      }
    }
    System.out.println("done");
  }

  public long getVal(long n) {
    if (n < 16) {
      return firsts[(int) n - 1];
    }
    if (memo.containsKey(n)) {
      return memo.get(n);
    }
    n -= 16;
    long ans;
    if (n % 3 == 0) {
      ans = (getVal(n / 48 * 3 + 1) << 4) | oneOrder[(int) (n / 3 % 16)];
    } else if (n % 3 == 1) {
      ans = (getVal(n / 48 * 3 + 2) << 4) | twoOrder[(int) (n / 3 % 16)];
    } else {
      ans = (getVal(n / 48 * 3 + 3) << 4) | threeOrder[(int) (n / 3 % 16)];
    }
    n += 16;
    memo.put(n, ans);
    return ans;
  }

  public void ntok() throws IOException {
    tok = new StringTokenizer(in.readLine());
  }

  public int ipar() {
    return Integer.parseInt(tok.nextToken());
  }

  public int[] iapar(int n) {
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = ipar();
    }
    return arr;
  }

  public long lpar() {
    return Long.parseLong(tok.nextToken());
  }

  public long[] lapar(int n) {
    long[] arr = new long[n];
    for (int i = 0; i < n; i++) {
      arr[i] = lpar();
    }
    return arr;
  }

  public double dpar() {
    return Double.parseDouble(tok.nextToken());
  }

  public String spar() {
    return tok.nextToken();
  }

  public static void main(String[] args) throws IOException {
    new C().go();
  }
}
