#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

ll X,Y,K;

void solve1()
{
    int b = 60;
    while((K & (1ll << b)) == 0) --b;
    ll ans = 0;
    while((Y >> (b+1)) - (X >> (b+1)) > 0)
    {
        if((X & K) == K) ++ans, ++X;
        else
        {
            ans += 2; X = (X | K) + 1;
        }
    }
    if(X != Y) ++ans;
    cout << ans << endl;
}

void solve2()
{
    int b = 60;
    while((K & (1ll << b)) == 0) --b;
    ll ans = 0;
    while((Y >> b) - (X >> b) > 1)
    {
        //printf("now X=%d, ans=%d\n",X,ans);
        if(X & (1ll << b))
        {
            ll mask = (1ll << b) - 1;
            if((X & mask) == mask)
            {
                ++ans; ++X;
            }
            else
            {
                ans += 2; X = (X | mask) + 1;
            }
        }
        else
        {
            ll mask = (1ll << (b+1)) - 1;
            if(((X & mask) ^ mask) <= K)
            {
                ans += 1; X |= mask;
            }
            else
            {
                X |= (1ll << b); ++ans;
            }
            // ll mask = (1ll << (b+1)) - 1;
            // if(((X & mask) ^ mask) <= K)
            // {
            //     ans += 2;
            //     X = (X | mask) + 1;
            // }
            // else
            // {
            //     mask = (1ll << b) - 1;
            //     if((X & mask) == mask)
            //     {
            //         ++ans; ++X;
            //     }
            //     else
            //     {
            //         ans += 2; X = (X | mask) + 1;
            //     }
            // }
        }
        //printf("now X=%d, ans=%d\n",X,ans);
    }
    if(X == Y)
    {
        cout << ans << endl;
        return;
    }
    if((X >> b) == (Y >> b))
    {
        cout << ans+1 << endl;
        return;
    }
    if((X ^ Y) <= K)
    {
        cout << ans+1 << endl;
        return;
    }
    if(X + 1 == Y)
    {
        cout << ans+1 << endl;
        return;
    }
    if(X & (1ll << b))
    {
        ll mask = (1ll << b) - 1;
        if((Y & mask) == 0)
        {
            cout << ans+2 << endl;
        }
        else if((X & mask) == mask)
        {
            cout << ans+2 << endl;
        }
        else
        {
            cout << ans+3 << endl;
        }
        return;
    }
    cout << ans+2 << endl;
}

void solve(){
    cin >> X >> Y >> K;
    if(X == Y) {cout << 0 << endl; return;}
    if(K == 1) {cout << abs(X-Y) << endl; return;}
    if(X > Y) swap(X, Y);
    if(X + 1 == Y) {cout << 1 << endl; return;}
    if((X ^ Y) <= K) {cout << 1 << endl; return;}
    ll tmpK = K + 1;
    if((tmpK & (-tmpK)) == tmpK)
    {
        solve1();        
    }
    else
    {
        solve2();
    }
}

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

/*

*/