#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);
    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;
    }
    pref /= (1ll << (bit + 1));
    // assert (pref != 0);

    int ans = 0;
    if (pref == 0) {
        if ((x ^ y) < k) ans++;
        else ans += 2;
    }
    else {
        if (k == (1ll << bit)) {
            // se for potencia de 2
            if (x == k - 1) ans++;
            else ans += 2;

            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();
}