#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;scanf("%d",&t);
    while(t--){
        ll x,y,k;scanf("%lld%lld%lld",&x,&y,&k);
        ll l=63-__builtin_clzll(k),r=3;
        if((1ll<<l+1)==k+1)r=2;
        if(!l||!(x^y)){
            printf("%lld\n",x^y);
            continue;
        }
        if((x^y)<=k){
            puts("1");
            continue;
        }l++;
        ll ans=0,mid=0;
        if(x<y){
            for(int i=0;i<l;i++){
                if(!(x>>i&1))
                mid+=1ll<<i,x+=1ll<<i;
            }
            if(mid)ans++;
            if(mid>k)ans++;
            if(x>=y){
                puts("2");
                continue;
            }
            ans++;x++;
            y-=x;
            ans+=y/(1ll<<l)*r;y%=(1ll<<l);
            if(y)ans++;
            if(y>k)ans++;
        }
        else {
            for(int i=0;i<l;i++){
                if(x>>i&1)
                mid+=1ll<<i,x-=1ll<<i;
            }
            if(mid)ans++;
            if(mid>k)ans++;
            if(x<=y){
                puts("2");
                continue;
            }
            ans++;x--;
            y=x-y;
            ans+=y/(1ll<<l)*r;y%=(1ll<<l);
            if(y)ans++;
            if(y>k)ans++;
        }
        printf("%lld\n",ans);
    }
}