#include <bits/stdc++.h>
using namespace std;

#define LOG(f...) fprintf(stderr, f)

using ll = long long;

ll K;
int pos;
ll lU;

ll opt(ll x) {
  ll cur = 1ULL << pos;
  for (int i = pos - 1; i >= 0; --i) {
    if ((x >> i) & 1) continue;
    if ((cur | (1ULL << i)) <= K) cur |= 1ULL << i;
  }
  return x ^ cur;
}

ll solve(ll x, ll y) {
  assert(x <= y);
  if (x == y) return 0;
  if ((x ^ y) <= K) return 1;
  if (y == x + 1) return 1;
  ll hx = x >> pos, hy = y >> pos;
  ll lx = x & lU;//, ly = y & lU;
  if (hy - hx > 1 && lx == 0) {
    ll cnt = (hy - hx) / 2; // -1 boundary?
    int nopt = ((K & lU) == lU ? 2 : 3);
    return cnt * nopt + solve(x + (cnt << (pos + 1)), y);
  }
  if (lx == lU) {
    if (hx & 1) return 1 + solve(x + 1, y);
    else if (hy - hx > 1) return 1 + solve(opt(x), y);
  }
  assert(hy > hx);
  if (hy - hx == 1) {
    if (hx & 1)
      return 2 + solve((hx + 1) << pos, y);
    else
      return 2;
  }
  if (hx & 1) return 2 + solve((hx + 1) << pos, y);
  else {
    { // lx != 0
      ll tx = opt(x);
      if ((tx & lU) == lU) return 2 + solve(tx + 1, y);
      else return 3 + solve((tx | lU) + 1, y);
    }
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    ll x, y;
    scanf("%lld%lld%lld", &x, &y, &K);
    if (x > y) swap(x, y);
    if (K == 0) { printf("%lld\n", y - x); continue; }
    pos = 63 - __builtin_clzll(K); lU = (1LL << pos) - 1;
    printf("%lld\n", solve(x, y));
  }
}