#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){
            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){
            int y=(m/(1ll<<x))-(n/(1ll<<x));
            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;
                }
            }
            if(m%(1ll<<x)) ans++;
            wt(ans);
        }
        else{
            int y=(n/(1ll<<x))-(m/(1ll<<x));
            if(k==(1ll<<x)-1){
                if(n%(1ll<<x)==0){
                    ans=y*2-1;
                }
                else{
                    ans=y*2;
                }
            }
            else{
                if(n%(1ll<<x)==0){
                    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;
                }
            }
            if(m%(1ll<<x)!=(1ll<<x)-1) ans++;
            wt(ans);
        }

	}
	return 0;
}