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

using ll = long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define pb push_back

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

int x, y, k;

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

    k++;
    // conseguimos todos os valores de [0, k)

    if (k < 3) {
        cout << abs (x - y) << "\n";
        return;
    }
    if (x == y) {
        cout << "0\n";
        return;
    }

    int bit = 63 - __builtin_clzll (k);
    // dbg (bit);
    if (x > y) swap (x, y);
    
    int pref = 0;
    for (int j = bit + 1; j < 61; j++) {
        int p = (1ll << j);
        if (p & y) pref += p, y -= p;
        if (p & x) pref -= p, x -= p;
    }
    // dbg (pref);
    pref /= (1ll << (bit + 1));
    // dbg (pref);

    int ans = 0;
    if (k == (1ll << bit)) {
        // se for potencia de 2
        if (x != k - 1) ans++;
        ans++;

        ans += 2 * (pref - 1); 
        if (y != 0) ans++;
    }
    else {
        // senao, temos que ligar o bit e ir passando para o proximo
        if (x == (1ll << (bit + 1)) - 1) ans++;
        else if ((x ^ (1ll << (bit + 1) - 1)) < k) ans += 2;
        else ans += 3;

        // dbg (ans);
        ans += 3 * (pref - 1);
        // dbg (ans);

        if (y == 0);
        else if (y < k) ans++;
        else ans += 2;
    }
    cout << ans << "\n";
}

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