#include<bits/stdc++.h>
#define MAXN 500010
#define INF 1000000010
#define MOD 998244353
#define LL long long
#define LLL __int128_t
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
void Main(){
	LL x,y,k;cin>>x>>y>>k;
	if (x>y) swap(x,y);
	if (k<=1){
		cout<<y-x<<"\n";
		return ;
	}
	if (x==y){
		cout<<0<<"\n";
		return ;
	}
	if ((x^y)<=k){
		cout<<1<<"\n";
		return ;
	}
	int len=0;
	For(i,1,61){
		len=i; 
		if ((1LL<<len)>k) break;
	}
	LL base=(1LL<<len);
	if (x/base==y/base){
		cout<<2<<"\n";
		return ;
	}
	int step=1;
	if (k==(base-1)) step=2;
	else step=3;
	LL ans=0;
	if (x%base==base-1) ans=1;
	else if (((base-1)^(x%base))<=k) ans=2;
	else ans=3;
	x=(x/base+1)*base;
	ans+=1LL*(y/base-x/base)*step;
	x=(y/base)*base;
	if (x==y);
	else if ((x^y)<=k) ans++;
	else ans+=2;
	cout<<min(ans,abs(y-x))<<"\n";
}
int main(){
	std::ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;cin>>T;
	while (T--) Main();
}
/*
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
*/