/**
 * @file qoj6510F1.cpp
 * @author n685
 * @brief
 * @date 2023-07-26
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr                                                                   \
  if (false)                                                                   \
  std::cerr
#endif

const int MX = 60;

void solve() {
  int64_t X, Y, K;
  cin >> X >> Y >> K;
  if (K <= 1) {
    cout << std::abs(X - Y) << '\n';
    return;
  }
  if (X == Y) {
    cout << "0\n";
    return;
  }
  if (X > Y)
    std::swap(X, Y);
  int m = std::__lg(K);
  int64_t ans = 0;

  {
    int64_t t = (X | ((1 << (m + 1)) - 1)) + 1;
    if ((X ^ t) <= K || t - X <= 1)
      ans++;
    else if (t - X <= 2 || (X ^ (t - 1)) <= K)
      ans += 2;
    else
      ans += 3;
    X = t;
  }

  ans += (Y / (1 << (m + 1)) - X / (1 << (m + 1))) *
         (K == (1 << (m + 1)) - 1 ? 2 : 3);

  X += (1 << (m + 1)) * (Y / (1 << (m + 1)) - X / (1 << (m + 1)));
  if (X != Y) {
    if ((X ^ Y) <= K || Y - X == 1) {
      ans++;
    } else
      ans += 2;
  }

  cout << ans << '\n';
}

int main() {
#ifdef LOCAL
  cin.open("input.txt");
  cout.rdbuf()->pubsetbuf(0, 0);
  cout.open("output.txt");
#else
  cin.tie(nullptr)->sync_with_stdio(false);
#endif

  int t;
  cin >> t;
  while (t--)
    solve();
}