#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"

int T=0;

void solve()
{
    int x,y,k;  cin>>x>>y>>k;
    if(x>y) swap(x,y);
    int len=0;
    int tmp=k;
    while(tmp!=0)
    {
        len++;
        tmp=tmp>>1;
    }
    int xl,xr,yl,yr;
    xl=x>>len;  xr=x-(xl<<len);
    yl=y>>len;  yr=y-(yl<<len);
    int m=3;    
    if(k==(1<<len)-1)   m=2;
    int t=(m*(yl-xl-1));
    if(t<0) t=0;
    
    int xxr=(1<<len)-1-xr;

    int a=((xxr)>k)?3:2;
    if(xr==((1<<len)-1))    a=1;
    int b=(yr>k)?2:1;
    if(yr==0)   b=0;
    int ans=t+a+b;
    if(x==0)    a=2;
    int cnt=0;
    for(int i=0;i<61;i++){
        if(((x>>i)&1)!=((y>>i)&1)){
            cnt+=(1<<i);
        }
    }
    if(cnt<=k)  ans=1;
    if(x==y)  ans=0;
    if(k<=1)    ans=(y-x);
    //ans=min(y-x,ans);
    //if(y-x==1)  ans=1;
    if(T==1000) cout<<t<<" "<<m<<" "<<b<<endl;

    cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
    while(T--)  solve();
    return 0;
}