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

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);
    int a=((~xr)>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=1;
    if(y==0)    b=0;
    if(k==1||k==0)    ans=(y-x);
    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;
    //cout<<t<<" "<<a<<" "<<b<<endl;

    cout<<ans<<endl;
}

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