#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 == 809) 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(X < 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++;
					else ans += 2;
				}
				ll cc = (py>>lk)-(px>>lk); 
				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 += 1;
					else ans += 2;
				}
				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

*/