#include <bits/stdc++.h>
using namespace std;
#define int long long 
int solve()
{
    int l,r,s;
    cin>>l>>r>>s;
    vector<int>a;
    while(l<=r&&(l%4!=0)){
        a.push_back(l);l++;
    }
    while(l<=r&&(r%4!=3)){
        a.push_back(r);r--;
    }
    sort(a.begin(),a.end());
    int siz=a.size(),ans=r-l+1;
    vector<vector<int>> dp(siz+1,vector<int>(siz+1,(int)8e18));
    dp[0][0]=0;
    // for(auto it:a)cout<<it<<" ";;cout<<endl;
    auto gmin = [&](int &x,int y){
        if(y<x)x=y;
    };
    for(int i=0;i<siz;i++){
        for(int j=0;j<=siz;j++){
            gmin(dp[i+1][j],dp[i][j]);
            if(j+1<=siz&&i+1<=siz)gmin(dp[i+1][j+1],dp[i][j]+a[i+1-1]);
            if(j+2<=siz&&i+2<=siz)gmin(dp[i+2][j+2],dp[i][j]+(a[i+1-1]^a[i+2-1]));
            if(j+3<=siz&&i+3<=siz)gmin(dp[i+3][j+3],dp[i][j]+(a[i+1-1]^a[i+2-1]^a[i+3-1]));
            // cout<<"i="<<i<<" j="<<j<<" dp="<<dp[i][j]<<endl;
        }
    }
    int mx=0;
    for(int i=0;i<=siz;i++)if(dp[siz][i]<=s)mx=i;
    ans+=mx;
    if(ans==0)return -1;
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;while(T--)cout<<solve()<<"\n";
}