#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <bitset>

using namespace std;
using ll = long long;
const int N = 2e6 + 5;

ll x, y, k;

int leftone(ll x) {
  int k = 0;
  while (x) {
    k++;
    x >>= 1;
  }

  return k;
}

ll solve() {
  cin >> x >> y >> k;
  if (y < x) swap(x, y);
  if (x == y) return 0;
  if (k == 0 || k == 1) return y - x;

  int lk = leftone(k);
  ll lhx = x >> lk;
  ll lhy = y >> lk;
  ll km = (1LL << lk) - 1;
  ll rhx = x & km;
  ll rhy = y & km;
  ll cnt = 0;
  if (lhx != lhy) {
    if (rhx == km) {
      rhx = 0;
      cnt++;
    } else {
      if (rhx >= ~k) cnt += 2;
      else cnt += 3;
    }
    rhx = 0;
    lhx++;
    cnt += (lhy - lhx) * 3;
  }
  
  if (rhx != rhy) {
   
    if (abs(rhy - rhx) == 1) cnt++;
    else {
      ll t = rhx ^ rhy;
      cnt += t > k ? 2 : 1;
    }
  }

  return cnt;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0);

  int t;
  cin >> t;
  while (t--) printf("%lld\n", solve());

  return 0;  
}