#include <bits/stdc++.h>

#define int long long

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 x, y, k;
    std::cin >> x >> y >> k;
    if (x > y) {
        std::swap(x, y);
    }
    if (x == y) {
        std::cout << "0\n";
        return;
    } 
    if ((x ^ y) <= k) {
        std::cout << "1\n";
        return;
    }
    if (k == 0) {
        std::cout << y - x << "\n";
        return;
    }
    int cnt = 0;
    int z = k;
    while (z != 0) {
        cnt++;
        z /= 2;
    }

    int ans = 0;
    int x1 = x % (1LL << cnt);
    int y1 = (1LL << cnt) - 1;
    int x2 = x >> cnt, y2 = y >> cnt;
    int y3 = y % (1LL << cnt);
    if (y2 == x2) {
    	std::cout << "2\n";
    	return;
    }
    if (x1 == y1) {
        ans += 0;
    } else if ((x1 ^ y1) <= k) {
        ans += 1;
    } else if ((x1 ^ y1) > k) {
        ans += 2;
    }
    ans++;
    x2++;
    int d = y2 - x2;
    if (k == y1) {
        ans += d * 2;
    } else {
        ans += d * 3;
    }
    assert(d >= 0);
    
    if (y3 == 0) {
        ans += 0;
    } else if (y3 > k) {
        ans += 2;
    } else {
        ans += 1;
    }
    std::cout << ans << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

    int T = 1;
    std::cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}