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

#define ff    first
#define ss    second
#define pb    push_back

typedef long long    ll;
typedef pair<ll,ll>    ii;
typedef long double    lf;


mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll SQ = 320;
const ll N = (1<<22);
const ll mod = 998244353;

ll x, y, k;

ll cost (ll a, ll b) {
  if (a == b) return 0;
  if ((a^b) <= k) return 1;
  return 2;
}

int main(){
  #ifdef LOCAL
  freopen("input.txt","r",stdin);
  #endif // LOCAL
  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);

  int t; cin >> t;
  while (t--) {

    cin >> x >> y >> k;
    if (x > y) swap(x, y);

    if (k <= 1) {
      cout << y - x << '\n';
      continue;
    }

    ll bk = 0;
    for (int i = 0; i < 60; ++i) {
      if (k & (1ll<<i)) bk = i;
    }
    ll msk = 0;
    for (int i = bk + 1; i < 60; ++i) msk |= (1ll<<i);

    ll nx = ((x & msk) >> (bk+1));
    ll ny = ((y & msk) >> (bk+1));

//    cout << bk << ' ' << (x&msk) << ' ' << (y&msk) << ' ' << nx << ' ' << ny << '\n';

    if (nx == ny) {
      cout << cost(x, y) << '\n';
    } else {
      ll allbk = (1ll<<(bk + 1)) - 1ll;
      ll ans = ny-nx + cost(x & allbk, allbk) + cost(0, allbk) * (ny - nx - 1) + cost(0, y & allbk);
      cout << ans << '\n';
    }

  }
  return 0;
}