#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()


ll calc ( ll up , ll down , ll mx ) {
    if ( up == down ) { return 0 ; }
    ll diff = ( up ^ down ) ;
    if ( diff <= mx ) { return 1 ; }
    return 2 ;
}

void solve ( ) {
    ll x , y , z ;
    cin >> x >> y >> z ;
    if ( x < y ) { swap ( x , y ) ; }
    ll up = 1 , id = 0 ;
    while ( up <= z ) {
        up *= 2 ;
        ++ id ;
    }
    ll bigx = ( x >> id ) , bigy = ( y >> id ) ;
    ll smallx = ( x & ( up - 1 ) ) , smally = ( y & ( up - 1 ) ) ;
    if ( bigx == bigy ) {
        cout << calc ( smallx , smally , z ) << "\n" ;
    }
    else {
        ll ret = bigx - bigy + calc ( smallx , 0 , z ) ;
        -- bigx ;
        ret += ( bigx - bigy ) * calc ( up - 1 , 0 , z ) ;
        ret += calc ( up - 1 , smally , z ) ;
        cout << ret << "\n" ;
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}