#include <array>
#include <cstddef>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <string>

namespace {
using std::cin;
using std::cout;
using std::int64_t;
using std::size_t;

namespace base {
template <typename T, size_t... sizes>
struct NestedArray {};

template <typename T, size_t size, size_t... sizes>
struct NestedArray<T, size, sizes...> {
  using Type = std::array<typename NestedArray<T, sizes...>::Type, size>;
};

template <typename T>
struct NestedArray<T> {
  using Type = T;
};

template <typename T, size_t... sizes>
using Array = typename NestedArray<T, sizes...>::Type;

void OptimizeIO() {
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
}

void OptimizeIO(const std::string &input_file, const std::string &output_file) {
  static std::ifstream input_stream(input_file);
  static std::ofstream output_stream(output_file);
  cin.rdbuf(input_stream.rdbuf()), cout.rdbuf(output_stream.rdbuf());
  cin.tie(nullptr), cout.tie(nullptr);
}
}  // namespace base

using base::Array;

int64_t x, y, k;
int m;

int Distance(int64_t x, int64_t y) {
  if (x == y) return 0;
  if ((x ^ y) <= k) return 1;
  return 2;
}

void Solve() {
  cin >> x >> y >> k;
  if (x > y) std::swap(x, y);
  m = 0;
  while ((int64_t{1} << m) <= k) ++m;
  int64_t a = x >> m, b = y >> m;

  if (a == b) {
    cout << Distance(x, y) << "\n";
  } else {
    cout << 1 + Distance(x, ((a + 1) << m) - 1) +
                (b - a - 1) * (Distance(0, (int64_t{1} << m) - 1) + 1) +
                Distance(b << m, y)
         << "\n";
  }
}

int Main() {
  base::OptimizeIO();
  int t;
  cin >> t;
  while (t--) Solve();
  return 0;
}
}  // namespace

int main() { return Main(); }