#include <bits/stdc++.h>

using namespace std;
#define int long long

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int _=1;
	cin>>_;
	while (_--){
		int x,y,k;
		cin>>x>>y>>k;
		if (x>y) swap(x,y);
		if ((x^y)<=k){
			cout<<min(y-x,1ll)<<'\n';
			continue;
		}
		vector <int> a(100,0),b(100,0),c(100,0);
		int tem=x,id=0;
		while (tem){
			a[id++]=tem%2;
			tem/=2;
		}
		for (int i=id;i<100;i++) a[i]=-id;
		tem=y,id=0;
		while (tem){
			b[id++]=tem%2;
			tem/=2;
		}
		for (int i=id;i<100;i++) b[i]=-id;
		tem=k,id=0;
		while (tem){
			c[id++]=tem%2;
			tem/=2;
		}
		for (int i=id;i<100;i++) c[i]=-id;
		if (b[99]==c[99]){
			cout<<min(2ll,y-x)<<'\n';
			continue;
		}
		vector <int> pl(62);
		pl[0]=1;
		for (int i=1;i<62;i++) pl[i]=pl[i-1]*2;
		int det=0;
		for (int i=-c[99];i<-b[99];i++){
			det+=pl[i+c[99]]*(b[i]-(a[i]<0?0:a[i]));
		}
//		cout<<det<<'\n';
		int bta=0;
		for (int i=-c[99];i<-a[99];i++){
			bta+=pl[i]*a[i];
		}
		int ans=0;
		if (x==bta) ans+=0;
		else if ((x-bta)==pl[-c[99]]-1) ans++;
		else if (((pl[-c[99]]-1)^(x-bta))<=k) ans+=2;
		else ans+=3;
		if (k==(pl[-c[99]]-1)) ans+=2*(det-(x!=bta));
		else ans+=3*(det-(x!=bta));
		det=0;
		for (int i=-c[99];i<-b[99];i++){
			det+=b[i]*pl[i];
		}
//		cout<<det<<'\n';
		tem=y;
		y-=det;
		if (!y) ans+=0;
		else if (y<=k) ans++;
		else ans+=2;
//		cout<<ans<<'\n';
		cout<<min(tem-x,ans)<<'\n';
//		cout<<'\n';
	}
}