#include <iostream>

using namespace std;

using ll = long long;

void sol() {
    ll X, Y, K;
    cin >> X >> Y >> K;
    if (X > Y) {
        swap(X, Y);
    }
    int len = 0;
    while ((1ll << len) <= K) ++len;
    if (K == 0) {
        cout << Y - X << '\n';
        return;
    }
    if (X == Y) {
        cout << 0 << '\n';
        return;
    }
    long long ans=0;
    if ((X >> len) == (Y >> len)) {
        if ((X ^ Y) <= K) {
            cout << 1 << '\n';
        } else {
            cout << 2 << '\n';
        }
    } else {
        ll g = (Y >> len) - (X >> len);
        ll st = (1ll << len) - 1;
        ll a = X & st;
        if(a==st){
            ans++;
        }
        else if ((a ^ st) <= K) {
            //cout<<"2222"<<
            ans+=2;
        }
        else{
            ans+=3;
        }
        if(st<=K)
        {
            ans+=2*(g-1);
        }
        else{
            ans+=3*(g-1);
        }
        if((Y &st)==0){
            
        }
        else if((Y &st)<=K){
            ans++;
        }
        else ans+=2;
        cout<<ans<<"\n";
    }

}

int main() {
    int T;
    cin >> T;
    while (T --) {
        sol();
    }
    return 0;
}