// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int MaxN = 2e5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

long long val(long long x){
    if (x & 1) return ((x + 1) / 2) & 1;
    return x ^ ((x / 2) & 1);
}

long long calc(long long L, long long R){
    return val(R) ^ val(L - 1);
}

void solve(){
    ll L, R, S; cin >> L >> R >> S;
    ll ans = -1;
    for (ll i = L; i < L + 5; ++ i){
        for (ll j = R; j > R - 5; -- j) if (i <= j && calc(i, j) <= S) maxl(ans, j - i + 1);
    }

    cout << ans << endl;
}

int main(){
    if (fopen("pqh.inp", "r")){
        freopen("pqh.inp", "r", stdin);
        freopen("pqh.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; cin >> t;
    while (t --) solve();
    return 0;
}