#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define endl '\n'
using namespace std;
using ll =long long ;
using pii =pair<int,int>;
using pll=pair<ll,ll>;
bool cmp(pll a,pll b){
	return a.y<b.y;
}
struct cmp1{
    bool operator()(pair<ll,ll>a,pair<ll,ll>b){
	if(a.x==b.x)return a.y>b.y;
	return a.x>b.x; 
}
};
const int mod=998244353;
ll ksm(ll a,ll b){ll ans=1;while(b){if(b&1){ans*=a;ans=ans%mod;}a=a*a;a%=mod;b>>=1;}return ans;}
ll gcd(ll a,ll b){ll t=a%b;while(t){a=b;b=t;t=a%b;}return b;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll get_inv(ll x){return ksm(x,mod-2);}
const int N=5e5+10;

void solve(){
	ll x,y,k;
	cin>>x>>y>>k;
	if((x^y)<=k){
		cout<<1<<endl;return ;
	}
	ll w=x^y;
	ll cnt=0;
	ll tx=x,ty=y;
	vector<ll>a(62);
	vector<ll>b(62);
	vector<ll>c(62);
	ll mx=0;
	for(ll i=0;i<=60;i++){
		if(w%2)mx=max(1ll<<i,mx);
		c[i]=w%2;w/=2;
		a[i]=tx%2;tx/=2;
		b[i]=ty%2;ty/=2;
	}
	ll ans=abs(x-y);
	if(mx<=k){
		ans=min(ans,2ll);
	}
	else{
		ll base=1;
		ll tk=k;
		while(tk){
			tk/=2;base*=2ll;
		}
		ll tx=x/base*base;ll ty=y/base*base;
		ll ci=(abs(tx-ty))/base;
		ll tans=(ci-1)*3ll+1;
		tx=x-tx;ty=y-ty;
		if(x>y){
			ty=base-ty-1;
		}
		else tx=base-tx-1;
		tans+=2;
		if(ty==0)tans--;
		if(tx==0)tans--;
		if(tx>k)tans++;
		if(ty>k)tans++;
		ans=min(ans,tans);
	}
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int _=1;
	cin>>_;
	while(_--)solve();
	return 0;
}