#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <array>
#include <queue>
#include <cmath>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int,int> PII;
const int N = 65,mod = 998244353,INF = 1e18;
int n,T,m,k;

void solve()
{
    cin >> n >> m >> k;
    if(n == m)
    {
        cout << 0 << endl;
        return ;
    }
    if(n ^ m <= k)
    {
        cout << 1 << endl;
        return ;
    }
    if(abs(n - m) == 1)
    {
        cout << 1 << endl;
        return ;
    }
    if(k == 0)
    {
        cout << abs(n - m) << endl;
        return ;
    }
    int cntk = 0,tmpk = k;
    while(k)
    {
        k >>= 1;
        cntk++;
    }
    int lown = n & ((1 << (cntk)) - 1);
    int lowm = m & ((1 << (cntk)) - 1);
    int highn = n >> cntk;
    int highm = m >> cntk;
    bool flag = (tmpk == ((1 << (cntk)) - 1));
    if(highn == highm)
    {
        int ans = 0;
        if(lown ^ lowm <= tmpk) ans = 1;
        else ans = 2;
        cout << ans << endl;
        return ;
    }
    else if(highn < highm)
    {
        int init = 0;
        if(lown == ((1 << (cntk)) - 1)) init = 1;
        else if(lown + tmpk >= (1 << (cntk)) - 1 || ((1 << (cntk)) - 2) == lown) init = 2;
        else init = 3;
        int ans = 0;
        if(flag) ans = init + (highm - highn - 1) * 2;
        else  ans = init + (highm - highn - 1) * 3;
        if(lowm == 0) ans = ans;
        else if(lowm <= tmpk || lowm == 1) ans = ans + 1;
        else ans = ans + 2;
        cout << ans << endl;
    }
    else{
        int init = 0;
        if(lown == 0) init = 1;
        else if(lown <= tmpk || lown == 1) init = 2;
        else init = 3;
        int ans = 0;
        if(flag) ans = init + (highn - highm - 1) * 2;
        else  ans = init + (highn - highm - 1) * 3;
        if(lowm == (1 << (cntk)) - 1) ans = ans;
        else if(lowm + tmpk >= (1 << (cntk)) - 1 || lowm == (1 << (cntk)) - 2) ans = ans + 1;
        else ans = ans + 2;
        cout << ans << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while(T--)
    {
        solve();
    }
}