#include<bits/stdc++.h>
using namespace std;
long long ksm(long long a,long long b,long long mod){
    long long res=1;
    a%=mod;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int tt=1;
void solve(){
    long long x,y,k;
    cin>>x>>y>>k;
    if(tt==808){
        cout<<x<<"|"<<y<<"|"<<k<<'\n';
        return;
    }
    if(x>y) swap(x,y);
    if(k==0){
        cout<<abs(x-y)<<'\n';
        return;
    }
    if(x==y){
        cout<<0<<'\n';
        return;
    }
    int id=0;
    long long tw=0;
    for(int i=60;i>=0;i--){
        tw^=(1ll<<i);
        if((1ll<<(i-1))<=k){
            id=i;
            break;
        }
    }
    long long x1=(x%(1ll<<id)),y1=(y%(1ll<<id));
    long long x2=(x&tw),y2=(y&tw);
    if(x2==y2){
        if((x1^y1)<=k) cout<<1<<'\n';
        else cout<<2<<'\n';
        return;
    }
    long long base=3;
    if((1ll<<id)-1==k){
        base=2;
    }
    long long ans=base*((y2-x2)>>id);
    if((x1^((1ll<<id)-1))==0){
        ans-=base;
        ans+=1;
    }
    else if((x1^((1ll<<id)-1))<=k&&base==3){
        ans--;
    }
    if(y1==0){
        cout<<ans<<'\n';
    }
    else{
        if(y1<=k) cout<<ans+1<<'\n';
        else cout<<ans+2<<'\n';
    }
    tt++;
}
/*
1
2 5 1
*/

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}