//c++ -Wall -std=c++14 -O2 -Wl,--stack=128000000
#include<bits/stdc++.h>
#define ll long long
#define pa pair<ll,ll>
#define ve vector<ll>
#define db double
#define pb push_back
#define py puts("Yes")
#define pn puts("No")
#define re register
#define rd read()
using namespace std;
const db eps=1e-5;
const ll mod=1e9+7,N=1000005,maxn=1ll<<60;
ll n,m,a,b,t,k,ans;
inline ll read(){
    ll x=0,f=1;static char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c-48);c=getchar();}
    return x*f;
}
ll wei(ll x){
	ll p=0;
	while(x){
		x>>=1;
		p++;
	}
	return p;
}
ll fan(ll x,ll k){
	ll p=0;
	for(int i=0;i<k;i++){
		p|=(((x>>i)&1)^1)<<i;
	}
	return p;
}
ll lastk(ll x,ll k){
	return x^((x>>k)<<k);
}
bool mod2(ll x){
	while(!(x&1)){
		x>>=1;
	}
	return x==1;
} 
signed main(){
	t=rd;
	while(t--){
		ans=0;
		a=rd,b=rd,k=rd;
		if(a==b){
			printf("%lld\n",ans);
			continue;
		}
		if(a>b)swap(a,b);
//		if(k<=1){
//			printf("%lld\n",b-a);
//			continue;
//		}
		if(a<b){
			ll w=wei(k)-1,p=lastk(a,w+1)+1;
			if(p-(p>>(w+1)<<(w+1))==0)ans++,a++;
			if(a==b){
				printf("%lld\n",ans);
				continue;
			}
			ll o=ans;
			if(mod2(k+1)){
				if((a^b)<=k){
					printf("%lld\n",ans+1);
					continue;
				}
				ans+=((b>>(w+1))-(a>>(w+1)))*2;
				if(lastk(b,w+1))ans++;
				printf("%lld\n",ans);
				continue;
			} 
			ans+=((b>>(w+1))-(a>>(w+1)))*3;
			if(ans-o==0){
				if((b^a)>k)ans+=2;
				else ans++;
				printf("%lld\n",ans);
				continue;
			}
			if(lastk(b,w+1)>k)ans+=2;
			else if(lastk(b,w+1))ans++;
			if(fan(lastk(a,w+1),w+1)<=k)ans--;
			printf("%lld\n",ans);
		}
	}
	return 0;
}