#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define ll long long
using namespace std;
const int B=60;
int T;
ll tmp,to_0[B+10],to_y[B+10];
ll qx,qy,K;
ll High(ll x){
  return 1ll<<(63-__builtin_clzll(x));
}
int Get(ll x){
  return 64-__builtin_clzll(x);
}
ll Solve0(ll x){
  //cout<<"SOLVE0 "<<x<<"\n";
  if(!x)return 0;
  ll hb=High(x);
  if(K>=x)return 1;
  else if(K>=High(x))return min(x,2ll);
  //cout<<"TO "<<x-hb<<"\n";
  return min(x,Solve0(x-hb)+1+to_0[Get(x)-1]);
}
ll Solve(ll x){
  if(x==qy)return 0;
  ll hb=High(x);
  ll t=(((qy)&((hb<<1)-1))^x);
  //cout<<"t="<<t<<"\n";
  if(K>=t)return 1;
  else if(K>=High(t))return min(x-qy,2ll);
  //cout<<"?,Get="<<Get(x)<<"\n";
  return min(x-qy,Solve0(x-hb)+1+to_y[Get(x)-1]);
}
int main() {
#ifdef popteam
  freopen("J.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  cin>>T;
  while(T--){
    cin>>qx>>qy>>K;
    if(qx<qy)swap(qx,qy);
    for(int i=1;(1ll<<i)-1<=qx;++i){
      to_0[i]=(1ll<<i)-1;
      if(K>=(1ll<<i)-1)to_0[i]=min(to_0[i],1ll);
      else if(K>=(1ll<<i-1))to_0[i]=min(to_0[i],2ll);
      else to_0[i]=min(to_0[i],(to_0[i-1]<<1)+1);
      tmp=(qy&((1ll<<i)-1));
      //cout<<"tmp="<<tmp<<"\n";
      if(tmp>=(1ll<<i-1))to_y[i]=to_y[i-1];
      else{
        tmp=((~qy)&((1ll<<i)-1));
        to_y[i]=(1ll<<i)-(qy&((1ll<<i)-1))-1;
        if(K>=tmp)to_y[i]=min(to_y[i],1ll);
        else if(K>=High(tmp))to_y[i]=min(to_y[i],2ll);
        else to_y[i]=min(to_y[i],to_0[i-1]+1+to_y[i-1]);
      }
      //cout<<"IN "<<i<<" to0="<<to_0[i]<<",toy="<<to_y[i]<<"\n";
    }
    cout<<Solve(qx)<<"\n";
  }
}
/*
8
4 5 0
5 8 3
9 2 6
15 28 5
97 47 8
164 275 38
114514 1919 810
0 1152921504606846975 1
*/