#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
inline int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
inline void solve(void) {
	int x,y,k;
	read(x),read(y),read(k);
	
	if (x==y) return puts("0"),void();
	if (!k) return printf("%lld\n",abs(x-y)),void();
	int d=__lg(k)+1;
	if (x>y) swap(x,y);//gdb(x,y,k,d);
	int tx=x&((1<<d)-1),ty=y&((1<<d)-1),ans=0;
	if ((x-tx)!=(y-ty)) {
		int tmp=tx^((1<<d)-1);
		if (tmp==0) ans=1,x++;
		else if (tmp<=k) ans=2,x+=tmp+1;
		else ans=3,x+=tmp+1;
//		gdb(x,y,ans,d,tmp,(y>>d)-(x>>d),(1<<d)-1);
		ans+=((y>>d)-(x>>d))*(2+(k!=(1<<d)-1));
		x=(y>>d)<<d;
	}
	tx=x&((1<<d)-1),ty=y&((1<<d)-1);
//	gdb(x,y,tx,ty,ans);
	if (tx==ty) ;
	else if ((tx^ty)<=k) ans+=1;
	else ans+=2;
	printf("%lld\n",ans);
}
signed main(void){
	int T;
	read(T);
	while (T--) solve();
	return 0;
}