#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define b(x) (1ll<<((x)-1))

ll i,j,k,n,m,t,res,x,y,msk,sb;

ll fuck1(ll x,ll y){
	ll t1=(x>>k),t2=(y>>k),sb;
	ll res=0;
	
	if((x&msk)==msk){
		res++; x++;
	}
	else{
		res+=2; x|=msk; x++;
	}
	
	sb=max(0ll,t2-t1-5);
	res+=sb*2;
	x+=sb*(msk+1);
	while((x^y)>m){
		x+=msk+1; res+=2;
	}
	if(x^y)res++;
	return res;
}

ll fuck2(ll x,ll y){
	k++;
	ll t1=(x>>k),t2=(y>>k),sb;
	ll res=0;
	
	if((x&(msk*2+1))==(msk*2+1)){
		res++; x++;
	}
	else if(x^(msk*2+1)<=m){
		res+=2; x|=(msk*2+1); x++;
	}
	else{
		res+=3; x|=(msk*2+2); x++;
	}
	//cout<<"NMSL "<<x<<' '<<res<<endl;
	
	sb=max(0ll,t2-t1-5);
	res+=sb*3;
	x+=sb*(msk*2+2);
	
	//cout<<"NMSLB "<<x<<' '<<res<<endl;
	
	while((x^y)>(msk*2+2)){
		x+=msk*2+2; res+=3;
	}
	
	//cout<<"NMSLC "<<x<<' '<<res<<endl;
	
	if((x^y)>m)res+=2;
	else if(x^y)res++;
	return res;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>t;
	while(t--){
		cin>>x>>y>>m; res=0;
		if(x==y){
			cout<<"0\n"; continue;
		}
		if(!m){
			cout<<llabs(x-y)<<'\n'; continue;
		}
		if(x>y)swap(x,y);
		k=__lg(m+1); msk=(1ll<<k)-1;
		
		if((x^y)<=m){
			cout<<"1\n"; continue;
		}
		
		//cout<<"NMSL "<<x<<' '<<y<<' '<<m<<' '<<msk<<endl;
		
		if(msk==m){
			res=fuck1(x,y);
		}
		else{
			res=fuck2(x,y);
		}
		
		cout<<res<<'\n';
	}
}