#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fr(i,a,b) for(int i=a;i>=b;i--)
#define py puts("Yes")
#define pn puts("No")
#define pt puts("")
#define pb push_back
#define wt(x) write(x),puts("")
#define wr(x) write(x) ,putchar(' ')
#define tx printf("fds")
#define mp make_pair
#define fi first
#define se second
inline int read(){
	int x=0,k=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') k=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-48;
		ch=getchar();
	}
	return x*k;
}
void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int power(int x,int y,int mod){
	int num=1;
	while(y){
		if(y&1) num=(num*x)%mod;
		x=x*x%mod;
		y>>=1;
	}
	return num;
}
int mul(int x,int y,int mod){
	int num=0;
	while(y){
		if(y&1) num=(num+x)%mod;
		x=(x+x)%mod;
		y>>=1;
	}
	return num;
}
const int N=1e6+7,mod=998244353;
int n,m,tot,cnt,ans,k;
int a[N],b[N];
char s[N];
signed main(){
	int tt=read();
	while(tt--){
		n=read();m=read();k=read();
        if((n^m)<=k||abs(n-m)<=1){
            wt(1);
            continue;
        }
        if(k==0){
            wt(abs(n-m));
            continue;
        }
        int x=0;
        int now=k;
        while(now){
            x++;
            now>>=1;
        }
        int ans=0;
        if(n>m) swap(n,m);
        int y=(m/(1ll<<x))-(n/(1ll<<x));
        if(y==0){
            wt(2);
            continue;
        }
        if(k==(1ll<<x)-1){
            if(n%(1ll<<x)==(1ll<<x)-1){
                ans=y*2-1;
            }
            else{
                ans=y*2;
            }
        }
        else{
            if(n%(1ll<<x)==(1ll<<x)-1){
                ans=y*3-2;
            }
            else {
                int p=0;
                fo(i,0,x-1){
                    if(!(n&(1ll<<i))) p+=(1ll<<i);
                }
                if(p<=k) ans=y*3-1;
                else ans=y*3;
            }
        }
        int p=0;
        fo(i,0,x-1){
            if((m&(1ll<<i))) p+=(1ll<<i);
        }
        if(p<=k&&p) ans++;
        else if(p)ans+=2;
        wt(ans);
	}
	return 0;
}