#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll x,y,k;
void solve(){
    scanf("%lld %lld %lld",&x,&y,&k);
    if(x==y){
        puts("0");
        return;
    }
    if(k<=1){
        printf("%lld\n",abs(x-y));
        return;
    }
    if((x^y)<=k){
        puts("1");
        return;
    }
    int L=0;
    while(k>>L) L++;
    int c=2-(k+1>>L);
    ll ans=0;
    if(x<y) swap(x,y);
    if(x>y){
        ll hx=x>>L,hy=y>>L;
        ll lx=x&(1ll<<L)-1,ly=y&(1ll<<L)-1;
        if(hx==hy){
            puts("2"); return;
        }
        if(!lx){
            hx--; ans++;
            lx=(1ll<<L)-1;
        }
        else if(lx<=k){
            hx--; ans+=2;
            lx=(1<<L)-1;
        }
        else{
            hx--; ans+=c+1;
            lx=(1<<L)-1;
        }
        if(hx==hy){
            if(lx!=ly){
                if((lx^ly)<=k) ans++;
                else ans+=2;
            }
            printf("%lld\n",ans);
            return;
        }
        ans+=(hx-hy)*(c+1);
        lx=(1<<L)-1;
        if(lx!=ly){
            if((lx^ly)<=k) ans++;
            else ans+=2;
        }
    }
    printf("%lld\n",ans);
}
int main(){
    int t; scanf("%d",&t);
    while(t--) solve();
    return 0;
}