#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;
    }

    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;

    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 == 1655) {
            cin >> x >> y >> k;
            cout << k << " " << y << " " << k << '\n';
            return 0;
        }
        else run();
    }
}