#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=60;
ll pw[N];
void work(){
    ll x,y,k;
    cin>>x>>y>>k;
    if(x>y) swap(x,y);
    if(x==y){
        puts("0");
        return;
    }
    if(x+1==y || (x^y)<=k){
        puts("1");
        return;
    }
    ll u=1;
    while(u<=k) u<<=1;
    ll rx=x%u,ry=y%u,tx=x/u,ty=y/u;
    //cout<<u<<" "<<rx<<" "<<ry<<endl;
    if(tx==ty){
        puts("2");
        return;
    }
    ll ans=(ty-tx);
    if(k==u-1) ans*=2;
    else ans*=3;
    if(k<u-1) {
        if ((rx ^ (u - 1)) <= k) ans--;
        if (rx == u - 1) ans--;
    }
    else{
        if(rx==u-1) ans--;
    }

    if(k<u-1) {
        if (ry == 0) ans += 0;
        else if (ry <= k) ans++;
        else ans += 2;
    }
    else{
        if(ry==0) ans+=0;
        else ans++;
    }
    cout<<ans<<endl;
}
int main(){
    for(ll i=0;i<N;i++) pw[i]=(1ll<<i);
    int T;
   // cout<<(3^4 <=8)<<endl;
    cin>>T;
    while(T--) work();
    return 0;
}