Perfect Triples CodeForces 1339E

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

1. Find the lexicographically smallest triple of positive integers (a,b,c)(a,b,c) such that
   • a⊕b⊕c=0a⊕b⊕c=0, where ⊕⊕ denotes the bitwise XOR operation.
   • aa, bb, cc are not in ss.
   Here triple of integers (a1,b1,c1)(a1,b1,c1) is considered to be lexicographically smaller than triple (a2,b2,c2)(a2,b2,c2) if sequence [a1,b1,c1][a1,b1,c1] is lexicographically smaller than sequence [a2,b2,c2][a2,b2,c2].
2. Append aa, bb, cc to ss in this order.
3. Go back to the first step.

You have integer nn. Find the nn-th element of ss.

You have to answer tt independent test cases.

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

Input

The first line contains a single integer tt (1≤t≤1051≤t≤105) — the number of test cases.

Each of the next tt lines contains a single integer nn (1≤n≤10161≤n≤1016) — the position of the element you want to know.

Output

In each of the tt 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 ss are 1,2,3,4,8,12,5,10,15,…

ACcode＃１

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int inf = 1e8;
const int mod = 1000000007;
const int mx = 100010; //check the limits, dummy
typedef pair<int, int> pa;
const double PI = acos(-1);
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
#define swa(a,b) a^=b^=a^=b
#define re(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define rb(i,a,b) for(int i=(b),_=(a);i>=_;i--)
#define clr(a) memset(a, 0, sizeof(a))
#define lowbit(x) ((x)&(x-1))
#define mkp make_pair
void sc(int& x) { scanf("%d", &x); }void sc(int64_t& x) { scanf("%lld", &x); }void sc(double& x) { scanf("%lf", &x); }void sc(char& x) { scanf(" %c", &x); }void sc(char* x) { scanf("%s", x); }
ll  m, n,t,x,k,ans=0,sum=0;
ll a,b,c;
void fuck(ll x) {
    ll now = 1;
    b = c = 0;
    while (x)
    {
        if (x % 4 == 1)b += 2 * now, c += 3 * now;
        if (x % 4 == 2)b += 3 * now, c += now;
        if (x % 4 == 3)b += now, c += 2 * now;
        x /= 4, now *= 4;
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        ll x = (n - 1) / 3 + 1;
        ll now = 1;
        a = 1;
        while (x>now)
        {
            x -= now;
            a *= 4;
            now *= 4;
        }
        a += x - 1;
        fuck(a);
        if (n % 3 == 1)cout << a << endl;
        if( n % 3 == 2 )cout<< b << endl;
        if (n % 3 == 0)cout << c << endl;
    }
    return 0;
}

 ACcode＃２

#include<bits/stdc++.h>
#include <array>
using namespace std;
using ULL = unsigned long long;
using UL = unsigned;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

template<class Ty>
using passive_queue = priority_queue<Ty, vector<Ty>, greater<Ty>>;

struct Problem {
    void Loop() {
        ULL N; cin >> N;
        UL dig = 0; while (1ull << (dig * 2) <= N) dig++;
        dig--;
        N -= (1ull << (dig * 2));
        ULL D = N / 3, I = N % 3;
        ULL ans = (I + 1) << (dig * 2);

        ULL Tb[4][3] = { {0,0,0}, {1,2,3}, {2,3,1}, {3,1,2} };
        rep(i, dig) {
            ans |= Tb[D & 3][I] << (i * 2);
            D >>= 2;
        }
        cout << ans << endl;
    }

    void Solve() {
        UL T; cin >> T;
        rep(t, T) Loop();
    }

    Problem();
};
int main() {
    unique_ptr<Problem> p(new Problem());
    p->Solve();
    return 0;
}
Problem::Problem() {
    cout << fixed << setprecision(10);
}