#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()};
}

void solve()
{
	ll l, r, s;
	cin >> l >> r >> s;
	ll L = (l-1)/4*4ll+4;
	ll R = r/4*4ll-1;
	ll 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);
		ans += anss;
	}
	
	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();
}