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.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
 import java.util.*;
public  class realfast implements Runnable 
  {
    private static final int INF = (int) 1e9;
    long in= (long)Math.pow(10,9)+7;
    long fac[]= new long[3000];
    public  void solve() throws IOException 
    {
      int t = readInt();
      for(int f =0;f<t;f++)
      {
        long n = readLong();

        n--;
        long rem =n%3;
        long len = (n/3)+1;
        long no =0;
        long range =1;
        while(true)
        {
           if(len<=range)
           {
            no = range+len-1;
            break; 
           }
           len= len-range;
           range = 4*range;
        }

        if(rem==0)
            out.println(no);
        else if(rem==1)
        {
            long ans =0;
            long cur =1;
            while(no!=0)
            {
                long lom = no%4;
                 if(lom==0)
                    ans= ans;
                 else if(lom==1)
                    ans= ans+ cur*2;
                else if(lom==2)
                    ans= ans+ cur*3;
                else
                    ans= ans+ cur;
                cur =cur*4;
                no=no/4;
            }
            out.println(ans);
        }
        else
        {
            long ans =0;
            long cur =1;
            while(no!=0)
            {
                long lom = no%4;
                 if(lom==0)
                    ans= ans;
                 else if(lom==1)
                    ans= ans+ cur*3;
                else if(lom==2)
                    ans= ans+ cur*1;
                else
                    ans= ans+ cur*2;
                cur= cur*4;
                no=no/4;
            }
            out.println(ans);
        }


      }
    } 
    
    public long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    int u ;
    int v ;
    int index;
    edge(int u1, int v1 , int index1)
    {
       this.u=u1;
       this.v=v1;
       this.index=index1;
    }
    public int compareTo(edge e)
    {
        return this.v-e.v;
    }
}
