#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll getval(ll p){
    if(p==0)return 0;
    if(p==1)return 1;
    if(p==2)return 3;
    if(p==3)return 0;
    p-=3;
    ll t=(p-1)/4+1;
    ll st=t*4;
    p-=(t-1)*4;
    if(p==1)return st;
    if(p==2)return 1;
    if(p==3)return st+3;
    return 0;
}
void solve(){
    ll l,r,s;
    cin>>l>>r>>s;
    l--;
    ll ans=-1;
    for(ll i=l;i<=l+20&&i<=r;i++){
        for(ll j=r;j>=r-20&&j>i;j--){
            if((getval(j)^getval(i))<=s){
                ans=max(ans,j-i);
            }
        }
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}