#include <bits/stdc++.h>
#ifdef CKISEKI
#define safe cerr<<__PRETTY_FUNCTION__\
    <<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
using std::cerr;
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif

using namespace std;

signed main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int T;
    cin >> T;

    while (T--) {
        int64_t X, Y, K;
        cin >> X >> Y >> K;
        if (X < Y) swap(X, Y);
        if (K == 0) {
            cout << X - Y << '\n';
            continue;
        }

        const int c = __lg(K) + 1;
        const int mask = (1 << c) - 1;

        int64_t sX = X >> c;
        int64_t sY = Y >> c;
        debug(sX, sY, c);
        if (sX == sY) {
            if ((X ^ Y) <= K) {
                cout << 1 << '\n';
            } else {
                cout << 2 << '\n';
            }
            continue;
        }

        debug(X, Y);
        int64_t ans = 0;
        if (X & mask) {
            // adjust X to sX << c
            if ((X & mask) <= K) {
                ans += 1;
            } else {
                ans += 2;
            }
        }
        debug(bitset<5>(X));
        debug(bitset<5>(Y));
        debug(X & mask, ans);

        ans += (sX - sY - 1) * (K == mask ? 2 : 3);
        // now sX = sY + 1
        // X = sX << c
        // we can always use 1 operation to reach Y
        ans += 1;
        ans += (Y & mask) != mask;

        cout << ans << '\n';

    }
}