#pragma GCC optimize("O3") #pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; #ifndef ONLINE_JUDGE #define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline; #else #define debug(x); #endif #define ll long long /* ------------------------Input Checker---------------------------------- */ long long readInt(long long l,long long r,char endd){ long long x=0; int cnt=0; int fi=-1; bool is_neg=false; while(true){ char g=getchar(); if(g=='-'){ assert(fi==-1); is_neg=true; continue; } if('0'<=g && g<='9'){ x*=10; x+=g-'0'; if(cnt==0){ fi=g-'0'; } cnt++; assert(fi!=0 || cnt==1); assert(fi!=0 || is_neg==false); assert(!(cnt>19 || ( cnt==19 && fi>1) )); } else if(g==endd){ if(is_neg){ x= -x; } if(!(l <= x && x <= r)) { cerr << l << ' ' << r << ' ' << x << '\n'; assert(1 == 0); } return x; } else { assert(false); } } } string readString(int l,int r,char endd){ string ret=""; int cnt=0; while(true){ char g=getchar(); assert(g!=-1); if(g==endd){ break; } cnt++; ret+=g; } assert(l<=cnt && cnt<=r); return ret; } long long readIntSp(long long l,long long r){ return readInt(l,r,' '); } long long readIntLn(long long l,long long r){ return readInt(l,r,'\n'); } string readStringLn(int l,int r){ return readString(l,r,'\n'); } string readStringSp(int l,int r){ return readString(l,r,' '); } /* ------------------------Main code starts here---------------------------------- */ const int B = 60; int sufl[B], sufg[B]; int prel[B], pree[B]; inline int bit(long long x, int p){ return (x >> p) & 1; } inline void compute1(long long L, long long P){ if(bit(L, 0)){ sufl[0] = sufg[0] = bit(P, 0)^1; }else{ sufl[0] = 1; sufg[0] = 0; } int nbits = bit(L, 0); for(int i = 1; i < B; i++){ if(bit(P, i) == 0){ sufl[i] = sufl[i - 1]; }else if(bit(L, i) == 0){ sufl[i] = 0; if(nbits == 0){ sufl[i] ^= 1; } }else{ sufl[i] = sufl[i - 1]; if(nbits == 0){ sufl[i] ^= 1; } } nbits += bit(L, i); if(nbits == 0){ sufg[i] = sufl[i]^1; }else{ sufg[i] = sufl[i]; } } } inline void compute2(long long L, long long P){ int cur = 1; for(int i = B - 1; i >= 0; i--){ if(cur && bit(P, i) && !bit(L, i)){ cur = 0; } pree[i] = cur; } if(bit(L, B - 1)){ prel[B - 1] = bit(P, B - 1)^1; }else{ prel[B - 1] = 1; } for(int i = B - 2; i >= 0; i--){ if(bit(L, i)){ if(bit(P, i)){ prel[i] = 0; }else{ prel[i] = pree[i + 1]; } }else{ prel[i] = prel[i + 1]; } } } inline long long computeAnswer(long long L, long long P){ compute1(L, P); compute2(L, P); long long ans = 0; for(int i = 0; i < B; i++){ int nodd; int neve; if(i == B - 1){ if(bit(P, i)){ nodd = 1; }else{ nodd = 0; } neve = 0; }else{ if(bit(P, i)){ if(bit(L, i)){ neve = prel[i + 1]^pree[i + 1]; }else{ neve = 0; } nodd = prel[i + 1]; }else{ if(bit(L, i)){ nodd = prel[i + 1]^pree[i + 1]; }else{ nodd = 0; } neve = prel[i + 1]^pree[i + 1]; } } if(i == 0){ if(nodd){ ans ^= (1LL << i); } }else{ int cnt = (nodd & sufl[i - 1])^(neve & sufg[i - 1]); if(cnt){ ans ^= (1LL << i); } } } return ans; } inline long long brute(long long K, long long P){ long long ret = 0; for(long long J = 1; J <= P; J++){ if(((K + P - J)&K) == K){ ret ^= J; } } return ret; } void stressTest(int BB){ mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); for(int i = 0; i < 100000; i++){ cout << "Testing " << i << "-th round with "; int K = rng()&((1 << BB) - 1); int P = rng()&((1 << BB) - 1); cout << "K = " << K << " and P = " << P << endl; assert(brute(K, P) == computeAnswer(((1 << BB) - 1)^K, P)); } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif // stressTest(20); ll Q = readIntLn(1,1e5); while(Q--){ ll K = readIntSp(0,1e18); ll P = readIntLn(1,1e18); if(K == 0){ cout << P << '\n'; continue; } K--; long long L = ((1LL << B) - 1)^K; cout << computeAnswer(L, P) << '\n'; } assert(getchar()==-1); return 0; }