#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);

    auto [k1, p1] = std::div(x, 1LL << (B + 1));
    auto [k2, p2] = std::div(y, 1LL << (B + 1));
    if (k1 == k2) {
        std::cout << std::abs(p1 - p2) << "\n";
        return;
    }
    i64 ans = k2 - k1;
    ans += (k2 - k1 - 1) * f(0, (1LL << (B + 1)) - 1);
    ans += f(p1, (1LL << (B + 1)) - 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;
}

answer.code: In function ‘void solve()’:
answer.code:32:29: error: call of overloaded ‘div(i64&, long long int)’ is ambiguous
   32 |     auto [k1, p1] = std::div(x, 1LL << (B + 1));
      |                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/cstdlib:79,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:42,
                 from answer.code:1:
/usr/include/stdlib.h:852:14: note: candidate: ‘div_t div(int, int)’
  852 | extern div_t div (int __numer, int __denom)
      |              ^~~
/usr/include/c++/13/cstdlib:181:3: note: candidate: ‘ldiv_t std::div(long int, long int)’
  181 |   div(long __i, long __j) _GLIBCXX_NOTHROW { return ldiv(__i, __j); }
      |   ^~~
/usr/include/c++/13/cstdlib:217:3: note: candidate: ‘lldiv_t __gnu_cxx::div(long long int, long long int)’
  217 |   div(long long __n, long long __d)
      |   ^~~
answer.code:33:29: error: call of overloaded ‘div(i64&, long long int)’ is ambiguous
   33 |     auto [k2, p2] = std::div(y, 1LL << (B + 1));
      |                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/include/stdlib.h:852:14: note: candidate: ‘div_t div(int, int)’
  852 | extern div_t div (int __numer, int __denom)
      |              ^~~
/usr/include/c++/13/cstdlib:181:3: note: candidate: ‘ldiv_t std::div(long int, long int)’
  181 |   div(long __i, long __j) _GLIBCXX_NOTHROW { return ldiv(__i, __j); }
      |   ^~~
/usr/include/c++/13/cstdlib:217:3: note: candidate: ‘lldiv_t __gnu_cxx::div(long long int, long long int)’
  217 |   div(long long __n, long long __d)
      |   ^~~