#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'

void solve()
{
    LL X, Y, K;
    cin >> X >> Y >> K;
    if (X == Y)
    {
        cout << 0 << endl;
    }
    else if ((X ^ Y) <= K)
    {
        cout << 1 << endl;
    }
    else if (K <= 1)
    {
        cout << abs(X - Y) << endl;
    }
    else
    {
        if (X > Y)
            swap(X, Y);
        // cerr << bitset<10>(X) << endl;
        // cerr << bitset<10>(Y) << endl;
        LL t = K;
        while (t & (t - 1))
            t &= (t - 1);
        LL v = 2;
        t *= 2;
        if (t - 1 == K)
            v--;

        LL hx = X / t;
        LL hy = Y / t;
        LL lx = X % t;
        LL ly = Y % t;
        LL ans = 0;

        // #define debug(x) std::cerr << #x << ": " << x << '\n';

        //         cerr << "t = " << t << endl;
        //         cerr << "lx = " << lx << " ly = " << ly << " hx = " << hx << " hy = " << hy << endl;

        if (hx == hy)
        {
            if ((lx ^ ly) <= K)
                cout << 1 << endl;
            else
                cout << 2 << endl;
            return;
        }
        if (lx == t - 1)
            ans += 1;
        else if ((lx ^ (t - 1)) <= K)
            ans += 2;
        else
            ans += 3;

        // debug(ans);
        hx++;

        // debug(v);
        ans += (hy - hx) * (v + 1);
        // debug(ans);
        if (ly == 0)
        {
        }
        else if (ly <= K)
            ans++;
        else
            ans += 2;
        cout << ans << endl;
        assert(ans <= (Y - X));
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--)
        solve();

    return 0;
}