#include <bits/stdc++.h>

using namespace std;

#define int long long
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

int s, t, k;
int solve() {
  s = read(), t = read(), k = read();
  if (s > t) swap(s, t);
  if (!k) return t - s;
  int d = __lg(k), all = (1ll << d + 1) - 1;
  if ((s >> d + 1) == (t >> d + 1)) {
    int x = s ^ t;
    return x <= k ? 1 : 2;
  }
  int ans = 0, cnt = (t >> d + 1) - (s >> d + 1);
  if ((s & all) == all) ans = 1;
  else if ((s & all) + k >= all) ans = 2;
  else ans = 3;
  if (0 + k >= all) ans += 2 * (cnt - 1);
  else ans += 3 * (cnt - 1);
  if ((t & all) == 0) ;
  else if ((t & all) <= k) ans += 1;
  else ans += 2;
  return ans;
}

signed main() {
  for (int tc = read(); tc; -- tc) {
    printf("%lld\n", solve());
  }
  return 0;
}