#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 3e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

void solve() {
    ll X, Y, K;
    cin >> X >> Y >> K;
    if (X > Y) swap(X, Y);
    if (K <= 1) return cout << Y - X << el, void();
    int n = log2(K);
    ll ans = ((Y >> n + 1) - (X >> n + 1)) * 3;
    if (!ans) {
        if (X == Y) ans = 0;
        else if ((X & Y) <= K || Y - X == 1) ans = 1;
        else ans = 2;
        cout << ans << el;
        return;
    }
    ll v = (1ll << n + 1) - 1;
    if ((X & v) == v) ans -= 2;
    else if ((X & v) >> n & 1) ans -= 1;
    else if (((X & v) ^ v) <= K) ans -= 1;
    if (Y & v) ++ans;
    if ((Y & v) > K) ++ans;
    // cout << (X & v) << el;
    cout << ans << el;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int tcase = 1;
    cin >> tcase;
    while (tcase--) solve();
}