#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,k;
void solve() {
    cin >> a >> b >> k;
    if(a > b) swap(a , b) ;
    if(k == 0) {
        cout << b - a << '\n' ; return ;
    }
    if(a == b) {
        cout << 0 << '\n' ; return ;
    }
    ll d = (1 << __lg(k) + 1) - 1;

    int c = __lg(k) + 1;
    if((b >> c) == (a >> c)) {
        if((a ^ b) <= k) {
            cout << 1 << '\n' ;
        }
        else cout << 2 << '\n' ;
        return ;
    }
    ll a1 = ((a | d) ^ a) ;
    ll ans = 0;
    if(a1 <= k & a1 != 0) ans++ ;
    else if(a1 != 0) ans += 2;

    // cout << a1 <<' ' << ans << '\n' ;
    ans += ((b >> c) - (a >> c)) + ((b >> c) - (a >> c) - 1) * (1 + (k != d)) ;
    // cout << a1 <<' ' << ans << '\n' ;

    ll b1 = ((b | d) ^ d) ^ b;
    // cout << b1 << '\n' ;
    if(b1 <= k && b1 != 0) ans++;
    else if(b1 != 0) ans += 2;
    cout << ans << '\n' ;
}
int main()
{
   // freopen("in.txt","r",stdin) ;
    int t ; 
    ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
    cin >> t;
    while(t--) solve() ;
}