#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define all(x) (x).begin(), (x).end()

#define int long long

ll xsum[70];

void solve2(ll l, ll r, ll s)
{
	ll ans = -1;
	for (ll i = l; i <= r; ++i) xsum[i-l+1] = xsum[i-l] ^ i;
	for (ll i = l; i <= r; ++i) for (ll j = i; j <= r; ++j) if (s >= (xsum[j-l+1] ^ xsum[i-l])) ans = max(ans, j-i+1ll);
	cout << ans << "\n";
}

void solve()
{
	ll l, r, s;
	cin >> l >> r >> s;
	if (r - l <= 32) 
	{
		solve2(l, r, s);
		return;
	}
	ll ans = 0;
	if (l == 1)
	{
		if (r==3) 
		{
			cout << 3 << "\n";
			return;
		}
		if (r > 3)
		{
			l = 4;
			ans = 3;
		}
	}
	ll L = (l-1)/4*4ll+4;
	ll R = (r+1)/4*4ll-1;
	ans += max(0ll, R-L+1);
	set<ll> o;
	assert(L < R);
	int xx=0;
	if (L-2>=l) L-=2, ++xx;
	if (R+2<=r) R+=2, ++xx;
	if (xx==2) ans += 4;
	else if (xx==1) if(s) s-=1, ans+=2;
	
	for (ll i = l; i < L; ++i) o.insert(i);
	for (ll j = R+1; j <= r; ++j) o.insert(j); 
	
	while (o.size())
	{
		ll x = *o.begin(); o.erase(x);
		if (s >= x) ++ans, s -= x;
	}
	if (ans == 0) --ans;
	cout << ans << "\n";
}

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