不用dijkstra也可以打表。最短路不必用dijkstra推出来，肯定是1直接走到n，这样二进制变化肯定是最少的（反正到最后肯定要变嘛）。然后再做一个前缀异或和，就可以打表了。

不过，不打表直接推也行。相邻的偶数和奇数，2k与2k+1的异或和肯定是1。

1->2 边权3

1->3 边权2

1->5 边权4

1->4 边权5

n为奇数的时候

比如n=5，1 2 3 4 5，可以看成1 （2 3）（4 5），结果分别是0 1 1，异或起来就是0。

比如n=7，1 2 3 4 5 6 7，可以看成1 （2 3）（4 5）（6 7），结果分别是0 1 1 1，异或起来就是1。

......依次类推

n为偶数的时候

比如n=4，1 2 3 4，可以看成1 （2 3） 4，结果分别是0 1 5，异或起来就是4。（即n本身）

比如n=6，1 2 3 4 5 6，可以看成1 （2 3）（4 5） 6，结果分别是0 1 1 7，异或起来就是7。（即n+1）

比如n=8，1 2 3 4 5 6 7 8，可以看成1 （2 3）（4 5）（6 7）8 ，结果分别是0 1 1 1 9，异或起来就是8。（即n本身）

......依次类推

懂了吗？

using namespace std;
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
// vector<int>pre(1e5+1,0);
// void init(){
//     for(int i=1;i<=1e5;i++)pre[i]=i^1;
//     for(int i=1;i<=1e5;i++)pre[i]^=pre[i-1];
//     for(int i=1;i<=100;i++)cout<<pre[i]<<' ';
// }
void solve(){
    int n;
    cin>>n;
    if(n%4==0)cout<<n<<endl;
    else if(n%4==1)cout<<0<<endl;
    else if(n%4==2)cout<<n+1<<endl;
    else if(n%4==3)cout<<1<<endl;
}
int main(){
    // init();
	int T=1;
	cin>>T;
	while(T--)
	solve();
}