#include<bits/stdc++.h>
#define LL long long
using namespace std;
int t;
LL lb(LL x){
	return x&(-x);
}
LL Get(LL x){
	LL a=-1;
	while(x){
		a=lb(x); x-=a;
	}
	return a;
}
LL Get1(LL x){
	int k=0;
	while(x!=1){
		k++; x>>=1;
	}
	return k;
}
int main(){
	//freopen("J.in","r",stdin);
	//freopen("J.out","w",stdout);
	scanf("%d",&t);
	while(t){
		
		LL X,Y,K;
		t--; scanf("%lld%lld%lld",&X,&Y,&K);
		if(t==99191) printf("%lld %lld",Y,K);
		if(Y<X) swap(X,Y);
		if(!K){
			printf("%lld\n",Y-X);
			continue;
		} 
		if(Y==X){
			printf("0\n"); continue;
		}
		LL x,y,a,b,k,w;  
		x=Get(X); y=Get(Y); k=Get(K);
		if(Y<=K){
			if(y!=k){
				printf("1\n"); continue;
			}
			else{ //最高位相等 
				if(x==y){  //有最高位 
					printf("1\n"); continue;	
				}
				else{
					printf(((Y^X)<=K)?"1\n":"2\n");	continue;
				}
			}
		}
		LL ans=0; LL w1,xx,Y1,w2,ww,X1,Y2,X2;
		if(K<=X){
			if(x<y){ //x的最高位低 
				w1=2ll*k-1; 
				if((w1^(X&w1))<=K) {
					ans+=((w1^(X&w1))!=0);
				}
				else{
					ans=2;  //凑出1111 
				} //这个地方有锅 
				//cout<<ans<<endl;
				Y1=(Y>>Get1(k)+1<<Get1(k)+1); //后面都是0
				//cout<<X<<' '<<Y<<' '<<k<<' '<<Get1(k)+1<<endl;
				X|=w1;
				Y2=(Y>>Get1(k)+1);
				X2=(X>>Get1(k)+1);
				ans++; X2++;
				//cout<<X2<<' '<<Y2<<endl;
				ans+=(Y2-X2)*(K==w1?2ll:3ll);
				//cout<<ans<<' '<<Y<<' '<<Y1<<endl;
				if(Y==Y1) {}
				else{
					if(((Y^Y1)<=K)) ans++;
					else {
						ans+=2; //?
					}
				}
				printf("%lld\n",ans);
				continue;
			}
			else{ //x==y
				w2=Y^X; 
				if(w2<=K){
					ans=1;
					printf("%lld\n",ans);
				continue;
				}
				ww=Get(w2);
				if(ww==k){ //最高位相等 
					ans+=2; 
					printf("%lld\n",ans);
					continue;
				}
				else{ //最高位低 
					w1=(2ll*k)-1;
					X1=X|w1;
					if(X1!=X){  //?
						ans++;
						if((X1^X)>K) ans++;
					} 
					X=X1;
					Y1=(Y>>Get1(k)+1<<Get1(k)+1);
					Y2=(Y>>Get1(k)+1);
					X2=(X>>Get1(k)+1);
					ans++; X2++;
					ans+=(Y2-X2)*(K==w1?2ll:3ll);
					X=Y1;
					if((X^Y)<=K){
						ans+=(X!=Y);
					}
					else{
						ans+=2;
					}
				}
			}
			printf("%lld\n",ans);
			continue;
		}
		if(X<K){
			if(k==y){  //最高位相等 
				ans+=((X^Y)<=K?1:2);
			}
			else{ //k<y x<=k 
				w1=(2ll*k)-1; 
				xx=w1^X;  //K>X
				if(xx){
					if(xx<=K) ans=1;
					else{
						ans+=2;
					}
				}
				X=X|(w1);
				Y1=(Y>>Get1(k)+1<<Get1(k)+1);
				Y2=(Y>>Get1(k)+1);
				X2=(X>>Get1(k)+1);
				ans++; X2++;
				ans+=(Y2-X2)*(K==w1?2ll:3ll);
				X=Y1;
				w2=Y1^Y;
				if(w2){
					if(w2<=K) ans++;
					else ans+=2;
				}
			}
			printf("%lld\n",ans);
			continue;
		}
	}	
}