#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int count(int k) {
    int num = 0;
    while (k) {
        k >>= 1;
        num++;
    }
    return num;
}


int getval(ll x, ll y, ll k) {
    ll mid = (x ^ y);
    if (mid == 0) return 0;
    if (abs(x - y) == 1) return 1;
    if (mid <= k) return 1;
    return 2;
}

void solve() {
    ll x, y, k;
    cin >> x >> y >> k;
    if (x == y) {
        cout << 0 << "\n";
        return;
    }
    if (k <= 1) {
        cout << abs(x - y) << "\n";
        return;
    }
    ll nk = count(k);
    ll dkz = (1 << (nk)) - 1;
    if (x > y) {
        ll high_cost = ((x >> nk) - (y >> nk));
        if (high_cost == 0) {
            ll need = (x & dkz) ^ (y ^ dkz);
            ll ans = getval(x & dkz, y & dkz, k);
            cout << ans << "\n";
            return;
        }

        ll d1 = getval(x & dkz, 0, k);
        ll mid = (high_cost - 1) * (dkz == k ? 1 : 2) + high_cost;
        ll d2 = getval(y & dkz, dkz, k);

        cout << d1 + mid + d2 << "\n";
        return;
    } else {
        ll high_cost = abs(((x >> nk) - (y >> nk)));
        if (high_cost == 0) {
            ll ans = getval(x & dkz, y & dkz, k);
            cout << ans << "\n";
            return;
        }
        ll d1 = getval(x & dkz, dkz, k);
        ll mid = (high_cost - 1) * (dkz == k ? 1 : 2) + high_cost;
        ll d2 = getval(y & dkz, 0, k);
        cout << d1 + mid + d2 << "\n";
        return;

    }


}

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

    return 0;
}
/*
5
2
1 2
3
2 3 1
4
1 4 3 2
5
1 5 2 3 4
6
1 2 3 4 5 6


 */