#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;cin>>t;
    while(t--){
        typedef long long ll;
        ll a,b,k;cin>>a>>b>>k;
        if(!k){
            cout<<labs(a-b)<<'\n';
            continue;
        }
        int z=__lg(k)+1;
        if(a>b) swap(a,b);
        ll w=(1ll<<z)-1;
        ll ans=0;
        if((a>>z)!=(b>>z)){
            if((a&w)==w) ans++;
            else if((~a&w)<=k)ans+=2;
            else ans+=3;
            ans+=((b>>z)-(a>>z)-1)*(2+(k!=w));
            a=b>>z<<z;
        }
        if(a==b);else
        if((a^b)<=k) ans++;
        else ans+=2;
        cout<<min(b-a,ans)<<'\n';
    }
}