#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define l(x) (x<<1)
#define r(x) (x<<1|1)
#define mpr make_pair
#define pb push_back
//mt19937_64 ra(time(0) ^ (*new char));
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
const ll SIZE = 200005;
const ll mod = 998244353;
ll T;
ll X, Y, K;
ll cnt;

inline ll rd(){
	ll x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		x = (x<<1) + (x<<3) + (ch^48);
		ch = getchar();
	}
	return x*f;
}

ll power(ll x, ll y){
	ll jl = 1;
	while(y){
		if(y & 1) jl = (jl * x) % mod;
		x = (x * x) % mod;
		y >>= 1;
	}
	return jl;
}

ll len(ll x){
	ll jl = 0;
	while(x){
		jl++;
		x >>= 1;
	}
	return jl;
}

int main(){
	T = rd();
	while(T--){
		cnt++;
		X = rd(), Y = rd(), K = rd(); ll ans = 0;
		if(cnt == 6124) cout << X  << Y << K << endl;
		if(K == 0){
			printf("%lld\n", abs(X-Y));
			continue;
		}
		if(X > Y) swap(X, Y);
		ll lk = len(K), lx = len(X), ly = len(Y);
		if(len(K) > len(Y)) printf("1\n");
		else{
			ll px = (X&(((1ll<<60)-1)-((1ll<<lk)-1)));
			ll py = (Y&(((1ll<<60)-1)-((1ll<<lk)-1)));
			if(px == py){
				ll jlx = (X&((1ll<<lk)-1));
				ll jly = (Y&((1ll<<lk)-1));
				if((jlx ^ jly) <= K) ans += min(1ll, abs(X-Y));
				else ans += min(2ll, abs(X-Y));
			}
			ll cc = (py>>lk)-(px>>lk);
//			cout << cc << endl; 
			if(cc >= 1){
				if((X>>(lk-1))&1){
					if((X&((1ll<<lk)-1)) == ((1ll<<lk)-1)) ans += 1;
					else ans += 2;	
				} 
				else{
					ll jlx = (X&((1ll<<lk)-1));
					if((jlx ^ ((1ll<<lk)-1)) <= K || (jlx&((1ll<<(lk-1))-1)) == ((1ll<<(lk-1))-1)) ans += 2;
					else ans += 3;
				}
//					cout << cc << " " << ans << endl;
				if(K == (1ll<<lk)-1) ans += (cc-1) * 2;
				else ans += (cc-1) * 3;
				ll jly = (Y&((1ll<<lk)-1));
				if((jly ^ ((1ll<<lk)-1)) == ((1ll<<lk)-1)) ans += 0;
				else if((!((Y>>(lk-1))&1)) || jly <= K) ans += min(1ll, jly);
				else ans += min(2ll, jly);
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

/*
8
4 5 0
5 8 3
9 2 6
15 28 5
97 47 8
164 275 38
114514 1919 810
0 1152921504606846975 1

*/