#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll high(ll x){
    for(int i=62;i>=0;i--){
        int bit = (x >> i) & 1;
        if(bit) return i+1;
    }
    return 0;
}
ll solve(){
    ll x,y,k,ans = 0;
    cin>>x>>y>>k;
    if(x > y) swap(x,y);
    if(k == 0) return y - x;
    ll hk = high(k);
    ll dx = x/(1ll << hk),dy = y/(1ll << hk);
    //100 101 
    ll lowx = x & ((1ll<<hk) - 1),lowy = y & ((1ll<<hk) - 1);
    ll oper = dy - dx;
    //
    //不同组之间的操作次数
    if(k + 1 == (1ll<<hk)) ans += 2 * oper;
    else ans += 3 * oper; 

    if(k+1 != (1ll<<hk) and (((1ll<<hk) - 1)^lowx) <= k) --ans;
    
    if(lowx + 1 == (1ll<<hk)) --ans;
    
    if(ans) lowx = 0;
    
    if(lowx == lowy) ans += 0;
    else if(((lowx ^ lowy) <= k) or abs(lowx - lowy) == 1) ans += 1;
    else ans += 2;
    if(ans == 0 and x != y) cout<<x<<"_"<<y<<"_"<<k<<endl;
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--) cout<<solve()<<'\n';
    return 0;
}