#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);
    /*
    k    10010
    lowx 00001
    第一个k为0而x为1的位置
    if lowx 

    01111->
    11100
    00101
    */
   //三次的可能会被变成两次
    
    ll oper = dy - dx;
    //
    //不同组之间的操作次数
    if(k + 1 == (1ll<<hk)) ans += 2 * oper;
    else ans += 3 * oper; 
    // cout<<lowx<<" "<<lowy<<" "<<dx<<" "<<dy<<" "<<ans<<endl;
    if(k+1 != (1ll<<hk) and (((1ll<<hk) - 1)^lowx) <= k) --ans;
    if(lowx + 1 == (1ll<<hk)) --ans;
    // cout<<ans<<endl;
    // 
    //0101 -> 1000
    //将高位变成相同的
    //下面讨论低位
    if(ans) lowx = 0;
    // cout<<lowx<<" "<<lowy<<" "<<ans<<endl;
    if(lowx == lowy) ans += 0;
    else if(((lowx ^ lowy) <= k) or abs(lowx - lowy) == 1) ans += 1;
    else ans += 2;
    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;
}