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

    const int N = 1e6 + 5;

    ll x, y, k;
    int a[100], b[100], c[100];

    void run(){
        cin >> x >> y >> k;

        if (x > y) swap(x, y);

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

        if ((x ^ y) <= k || x + 1 == y) {
            cout << "1\n";
            return ;
        }

        ll cntx = 0, cnty = 0, cntk = 0;
        ll t = x;
        while (t) {
            a[++ cntx] = (t & 1);
            t >>= 1;
        }

        t = y;
        while (t) {
            b[++ cnty] = t & 1;
            t >>= 1;
        }

        bool ok = 0;
        t = k;
        while (t) {
            c[++ cntk] = t & 1;
            if (!c[cntk]) ok = 1;
            t >>= 1;
        }

        int cost = ok + 2;

        ll res = 0;
        for (int i = cnty; i > cntk; i -- ) {
            if (b[i] == 1) res += (ll)pow(2, i - cntk - 1) * cost;
            if (a[i] == 1) res -= (ll)pow(2, i - cntk - 1) * cost;
        }
        
        if (res > 0) {
            ll tmp = 1, sum = 0;
            for (int i = 1; i <= cntk; i ++ ) {
                if (!a[i]) sum += tmp;
                tmp <<= 1;
            }
            
            if (sum == 0) res = res - cost + 1;
            else if (sum <= k) res = res - cost + 2;

            tmp = 1, sum = 0;
            for (int i = 1; i <= cntk; i ++ )  {
                if (b[i]) sum += tmp;
                tmp <<= 1;
            }

            if (sum > k) res += 2;
            else res += sum != 0;
        }
        else {
            ll sum1 = 0, sum2 = 0, tmp = 1;
            for (int i = 1; i <= cntk; i ++ ) {
                if (a[i]) sum1 += tmp;
                if (b[i]) sum2 += tmp;
                tmp <<= 1;
            }

            res = (sum1 ^ sum2 <= k ? 1 : 2);
        }
        

        cout << res << '\n';
        for (int i = 1; i <= cnty; i ++ ) a[i] = b[i] = c[i] = 0;
    }    

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

        int tcase = 1;
        cin>>tcase;
        // while(tcase--) run();
        for (int i = 1; i <= tcase; i ++ ) {
            if (i == 1992) {
                cin >> x >> y >> k;
                cout << y << '\n';
            }
            else run();
        }
    }