#include <bits/stdc++.h>

using i64 = int64_t;

namespace stdr = std::ranges;
namespace stdv = std::views;

void solve() {
    i64 x, y, k;
    std::cin >> x >> y >> k;
    if (x > y) {
        std::swap(x, y);
    }

    if (k == 0 || x == y) {
        std::cout << y - x << "\n";
        return;
    }

    auto f = [&](i64 x, i64 y) {
        if (x == y) {
            return 0;
        }
        if (std::abs(x - y) == 1 || (x ^ y) <= k) {
            return 1;
        }
        return 2;
    };

    const int B = std::__lg(k);
    const i64 P = 1LL << (B + 1);

    auto [k1, p1] = std::div(x, P);
    auto [k2, p2] = std::div(y, P);
    if (k1 == k2) {
        std::cout << std::abs(p1 - p2) << "\n";
        return;
    }
    i64 ans = k2 - k1;
    ans += (k2 - k1 - 1) * f(0, P - 1);
    ans += f(p1, P - 1);
    ans += f(0, p2);

    std::cout << ans << "\n";
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}