/*

Author: Haze

2024/9/2

*/

#include <bits/stdc++.h>

#define irep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define drep(i, r, l) for(int i = (r); i >= (l); -- i)
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr);
using namespace std;
typedef long long ll;
#define int long long
inline ll readL() {
    ll s = 0;
    bool fl = false;
    char ch = (char) getchar();
    while (!isdigit(ch)) {
        if (ch == '-')fl = true;
        ch = (char) getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + (ch ^ 48);
        ch = (char) getchar();
    }
    return fl ? -s : s;
}

inline int read() {
    return (int) (readL());
}

const int mod = 1000000000 + 7;
const int itinf = 1000000999;
const ll llinf = 2e18;
const int N = 500099;

void solve() {
    ll x = read(), y = read(), k = read(), ans = abs(x - y);
    ll B = 2 << __lg(k );
    if(k < 2){
        cout << ans << '\n';
        return;
    }
    if(x < y){
        if(x / B == y / B){
            if((x ^ y) <= k)ans = 1;
            else ans = 2;
            cout << ans << '\n';
        }
        else{
            ll z = x % B;
            ll sum = B - 1 - z;
            sum = min(sum, 2ll);
            if(((B - 1) xor z) <= k)sum = min(sum, 1ll);
            x |= (B - 1);
            ++ x;
            sum ++;
            sum += (y / B - x / B) * (k == B - 1 ? 2 : 3);
            y %= B;
            sum += min(y, y <= k ? 1ll : 2ll);
            cout << min(ans, sum) << endl;
        }
    }
    else{
        if(x / B == y / B){
            if((x ^ y) <= k)ans = 1;
            else ans = 2;
            cout << ans << '\n';

        }
        else{
            ll z = x % B;
            ll sum = min(x % B, x % B <= k ? 1ll: 2ll);
            x -= z;
            -- x;
            sum ++;
            sum += (x / B - y / B) * (k == B - 1 ? 2 : 3);
            y %= B;
            y ^= (B - 1);
            sum += min(y, y <= k ? 1ll : 2ll);
            cout << min(ans, sum) << endl;
        }
    }
}

signed main() {
    // IOS
    int T = read();
    while (T--) {
        solve();
    }
    return 0;
}