#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
#define pb push_back
#define endl "\n"
/*
5
41 18467 6334
7
26500 19169 15724
1
11478 29358 26962
1
24464 5705 28145
1
23281 16827 9961
1
*/
void solve()
{
    ll x, y, k;
    cin>>x>>y>>k;
    //x=rand(), y=rand(), k=rand();
    if((!k) || k==1) {cout<<abs(x-y)<<endl;return ;}
    ll tmp = x^y;
    if(tmp<=k){
        cout<<"1\n";
        return;
    }
    bitset<70>xx(x), yy(y), kk(k);
    int m = 69;
    while(m>=0 && kk[m]==0) m--;
    m++;
    ll d=(y>>m)-(x>>m), ans=0;
    if(d>0){//x<y
        //先变全1
        ll m1=(1ll<<m)-1;
        ll sub=m1^(m1&x);
        if(!sub);
        else if(sub<=k) ans++;
        else if(sub>k) ans+=2;
        ans++, d--;
        ll bs=0;
        if(k==m1) bs=2;
        else bs=3;
        ans+=bs*d;
        x=0;
    }
    else if(d<0){
        //先全变0
        ll m1=(1ll<<m)-1;
        ll sub=m1&x;
        if(!sub);
        else if(sub<=k) ans++;
        else if(sub>k) ans+=2;
        ans++, d++;
        ll bs=0;
        if(k==m1) bs=2;
        else bs=3;
        ans-=bs*d;
        x=m1;
    }
    //printf("%lld===\n", ans);
    ll m1=(1ll<<m)-1;
    y = y&m1, x = x&m1;
    ll cost=x^y;
    if(!cost);
    else if(cost<=k) ans++;
    else if(cost>k) ans+=2;
    cout<<min( ans, abs(x-y)) <<endl;
}

signed main()
{
    #ifdef ONLINE_JUDGE
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    #endif
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}