#include <bits/stdc++.h> using namespace std; 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); // stressTest(20); int Q; cin >> Q; while(Q--){ long long K; cin >> K; long long P; cin >> P; if(K == 0){ cout << P << '\n'; continue; } K--; long long L = ((1LL << B) - 1)^K; cout << computeAnswer(L, P) << '\n'; } return 0; }