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

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

pair<set<ll>, ll> chk(ll l, ll r)
{
	set<ll> tmp;
	if (l%2==1) tmp.insert(l);
	if (r%2==0) tmp.insert(r);
	return {tmp, r-l+1-(ll)tmp.size()};
}


ll xsum[70];

void solve2(ll l, ll r, ll s)
{
	ll ans = -1;
	for (int i = l; i <= r; ++i) xsum[i-l+1] = xsum[i-l] ^ i;
	for (int i = l; i <= r; ++i) for (int 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;
	vector<pair<ll, ll>> tmp;
	if (L>R) tmp.push_back({l, r});
	else 
	{
		if (l < L) tmp.push_back({l, L-1});
		if (R < r) tmp.push_back({R+1, r});
	}
	for (auto [tl, tr] : tmp) 
	{
		auto [oo, anss] = chk(tl, tr);
		// cerr << tl << " " << tr << " " << anss << "\n";
		for (auto x : oo) o.insert(x);
		assert(anss % 2 == 0);
		ll _tmp = min(anss/2, s);
		ans += _tmp * 2;
		s -= _tmp;
	}
	
	while (o.size())
	{
		ll x = *o.begin(); o.erase(x);
		if (s >= x) ++ans, s -= x;
	}
	if (ans == 0) --ans;
	cout << ans << "\n";
}

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