#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6 + 5;

int a,b,k,sa,sb,sk,ans;

vector<int> A;
vector<int> B;
vector<int> K;

void run()
{
    A.clear();B.clear();K.clear();
    cin>>a>>b>>k;
    if (a> b) swap(a, b);

    if (k <= 1 || a == b) {
        cout << abs(a - b) << '\n';
        return ;
    }

    if ((a ^ b) <= k || a + 1 == b) {
        cout << "1\n";
        return ;
    }
    ans = 0;
    if(a<b){
        while(b){
            B.push_back(b%2);
            b/=2;
            A.push_back(a%2);
            a/=2;
        }
        while(k){
            K.push_back(k%2);
            k/=2;
        }
        // reverse(A.begin(),A.end());reverse(B.begin(),B.end());reverse(K.begin(),K.end());
        sa=A.size(),sb=B.size(),sk=K.size();int f=0,c=2,x=0,y=0;
        
        for(int i=sk-1;i>=0;i--){
            x*=2;x+=A[i];
            y*=2;y+=K[i];
            f*=2;f+=1;
            if(K[i]==0)c*=0;
        }
        if(x==f)ans++;else if((f^x)<=y)ans+=2;else ans+=3;

        // cout<<x<<" "<<(f^x)<<" "<<y<<'\n';
        // cout<<ans<<'\n';
        if(c==0)c=3;
        x=0,y=0;A[sk]++;
        for(int i=sb-1;i>=sk;i--){
            x*=2;x+=B[i];
            if(i<sa)y*=2;y+=A[i];
            
            // cout<<B[i]<<" ";
        }
        x-=y;ans+=x*c;
        // cout<<x<<"\n";
        // cout<<c<<'\n';
        // cout<<ans<<'\n';                                       
        x=0,y=0;
        for(int i=sk-1;i>=0;i--){
            x*=2;x+=B[i];
            y*=2;y+=K[i];
        }
        // cout<<x<<" "<<y<<'\n';
        if(x==0)ans=ans;else if(x<=y)ans++;else ans+=2;
        cout<<ans<<'\n';

    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int tcase = 1;
    cin >> tcase;
    while (tcase--)
        run();
}