#include <bits/stdc++.h>
using namespace std;
#define MAXN 4000006
#define LL long long
#define For(i, a, b) for(int i = (a); i <= (b);i++)
#define Rof(i, a, b) for(int i = (a); i >= (b);i--)
using namespace std;
LL x,y,k;
int getlen(LL x){
    int ans=0;
    while (x) x/=2,ans++;
    return ans;
}
void Main(){
    cin>>x>>y>>k;
    if (x>y) swap(x,y);
    if (k==0){
        cout<<y-x<<"\n";
    }
    if (x==y){
        cout<<0<<"\n";
        return ;
    }
    if ((x^y)<=k||y-x<=1){
        cout<<1<<"\n";
        return ;
    }
    int len=getlen(k);
    int step,first;
    LL mod=(1LL<<len);
    if (k==mod-1) step=2;
    else step=3;
    if (x%mod==mod-1) first=1;
    else if ((x%mod)^(mod-1)<=k) first=2;
    else first=3;
    if (y/mod==x/mod||y-x<=2){
        cout<<2<<"\n";
        return ;
    }
    // printf("first=%d step=%d\n",first,step);
    LL ans=((y/mod)-(x/mod)-1)*step+first;
    // printf("first=%d step=%d ans=%lld\n",first,step,ans);
    if (y%mod==0);
    else if (y%mod>0&&y%mod<=k) ans++;
    else ans+=2;
    cout<<ans<<"\n";
}
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while (T--) Main();
}
/*
 8
 4 5 0
 5 8 3
 9 2 6
 15 28 5
 97 47 8
 164 275 38
 114514 1919 810
 0 1152921504606846975 1
*/