#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"

void solve()
{
    ll x, y, k;
    cin>>x>>y>>k;
    bitset<62>xx(x), yy(y), kk(k);
    int m = 61;
    while(m>=0 && kk[m]==0) m--;
    m++;
    ll d=-(x>>m)+(y>>m), ans=0;
    if(d>0){
        //先变全1
        ll m1=(1ll<<m)-1;
        ll sub=m1^(m1&x);
        if(sub<=k&&sub) 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<=k&&sub) 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<=k&&cost) ans++;
    else if(cost>k) ans+=2;
    cout<<ans<<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;
}