/*
* @Author: zxxzy
* @Date:   2023-07-20 15:10:02
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <set>
#include <cmath>
#include <vector>
#include <map>
#define int long long
#define space ' '
#define endl '\n'
#define de(x) cout<<"** "<<x<<" **"<<endl;
#define N 200005
using namespace std;
using ll=long long;
const int mod=998244353;
const int INF=0x3f3f3f3f;
const double eps=1e-6;


signed main(){
    #ifdef LOCAL
        freopen("D:\\code2023\\test\\input.txt", "r", stdin);
        freopen("D:\\code2023\\test\\output.txt", "w", stdout);
    #endif
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int x,y,k;
        cin>>x>>y>>k;
        if(x>y){
            swap(x,y);
        }
        if(k<=1){
            cout<<y-x<<endl;
            continue;
        }
        int base=1;
        while(base<=k){
            base<<=1;
        }
        int ans=0;
        int xy=y/(base)-(x+base-1)/(base);
        if(k!=base-1){
            ans+=xy*3;
        }else{
            ans+=xy*2;
        }

        if(y/base==x/base){
            if(y==x){
                cout<<0<<endl;
            }else if((y^x)<=k){
                cout<<1<<endl;
            }else{
                cout<<2<<endl;
            }
            continue;
        }
        if(x%base==0){

        }else if(x%base==base-1){
            ans+=1;
        }else if(x%base<base-1-k){
            ans+=3;
        }else{
            ans+=2;
        }
        if(y%base==0){

        }else if(y%base<=k){
            ans+=1;
        }else{
            ans+=2;
        }
        cout<<ans<<endl;
    }

    return 0;
}