#include <bits/stdc++.h>

using namespace std;
#define dbg(x...) \
    do { \
        cout << #x << " -> "; \
        err(x); \
    } while (0)

void err() {
    cout << endl;
}

template<class T, class... Ts>
void err(T arg, Ts &... args) {
    cout << arg << ' ';
    err(args...);
}

typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10, Log = 20, inf = 0x3f3f3f3f;

ll x2y(ll x, ll y, ll k){
    if(x == y) return 0;
    ll r = x ^ y;
    if(r <= k) return 1;
    return 2;
}

void solve() {
    ll x, y, k;
    cin >> x >> y >> k;
    if(x > y) swap(x, y);
    int p = 60;
    for(ll i = 0, q = 1; i < 60; i++, q <<= 1){
        if(q > k){
            p = i;
            break;
        }
    }
    ll px = x >> p, py = y >> p;
    ll t = (1ll << p) - 1;
    ll qx = x & t, qy = y & t;
    if(px == py){
        cout << x2y(qx, qy, k) << "\n";
        return;
    }
    // px < py
    ll ans = x2y(qx, t, k) + 1;
    px++;
    ll r = x2y(0, t, k) + 1;
    ans += (py - px) * r;
    ans += x2y(0, qy, k);
    cout << ans << "\n";
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> T;
    while (T--) solve();
    return 0;
}