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

const int N = 1e6 + 5;

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

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

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

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

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

    if (k <= 1) {
        cout << abs(x - y) << '\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;
    int lenx = cntx, lenk = cntk;
    while (++ cntx < cnty) a[cntx] = 0;
    while (++ cntk < cnty) c[cntk] = 0; 

    ll res = 0;
    for (int i = cnty; i > lenk; i -- ) {
        if (b[i] == 1) res += pow(2, i - lenk - 1) * cost;
        if (a[i] == 1) res -= pow(2, i - lenk - 1) * cost;
    }

    ll tmp = 1, sum = 0;
    for (int i = 1; i <= lenk; 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 <= lenk; 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();
}