#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL t,a,b,c;
int main(){
	scanf("%lld",&t);
	while (t--){
		scanf("%lld%lld%lld",&a,&b,&c);
		if (a<b) swap(a,b);
		LL tmp=0,res=0;
		while ((1ll<<tmp)-1<c) tmp++;
		if ((a>>tmp)!=(b>>tmp)){
			res+=(a>>tmp)-(b>>tmp);
			if (c==0) res+=0;
			else if (c!=(1ll<<tmp)-1) res+=2*((a>>tmp)-(b>>tmp)-1);
			else res+=(a>>tmp)-(b>>tmp)-1;
			int tmpp=(a>>tmp)<<tmp;
			if (a==tmpp) res+=0;
			else if (((a^tmpp)<=c)||(a-1==tmpp)) res+=1;
			else res+=2;
			tmpp=(((b>>tmp)+1)<<tmp)-1;
			if (b==tmpp) res+=0;
			else if (((b^tmpp)<=c)||(b+1==tmpp)) res+=1;
			else res+=2;
		}
		else{
			if (a==b) res=0;
			else if (((a^b)<=c)||(a-1==b)) res=1;
			else res=2;
		}
		printf("%lld\n",res);
	}
}