#include <bits/stdc++.h>
#define int long long
#define ll long long
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(int i=(s);i>=(t);i--)

using namespace std;

int ci(){ int x; scanf("%lld", &x); return x; }

enum{N=100023};

int a[N], lastpos[N];

#define highbit(i) (int)(log2(i+0.5)+1)

signed main(){
	int T = ci();
	while( T-- ){
		int x = ci(), y = ci(), k = ci();
		if( x>y ) swap(x,y);
		int t = highbit(k);
		int ans = 0;
		if( k==0 ){
			ans = y-x;
		} else if( (x>>t) == (y>>t) ){
			if( (y^x) <= k ) ans++;
			else ans += 2;
		} else if( highbit(k) == highbit(k+1) ){
			if( (x>>t) != ((x+1)>>t) ) ans++;
			else{
				int f = (1ll<<t)-1 - (x & ((1ll<<t)-1));
				if( f <= k ) ans += 2;
				else ans += 3;
			}
			ans += max(0ll, (y>>t) - (x>>t) - 1) * 3;
			int u = y & ((1ll<<t)-1);
			if( u <= k ) ans++;
			else ans += 2;
		} else {
			if( (x>>t) != ((x+1)>>t) ) ans++;
			else ans += 2;
			ans += max(0ll, (y>>t) - (x>>t) - 1) * 2;
			if( y & ((1ll<<t)-1) ) ans++;
		}
		printf("%lld\n", ans);
	}
	return 0;
}