#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 xor Y) <= K)
    {
        cout << 1 << endl;
    }
    else if (K == 0)
    {
        cout << abs(X - Y) << endl;
    }
    else
    {
        if (X > Y)
            swap(X, Y);
        // cerr << bitset<6>(X) << endl;
        // cerr << bitset<6>(Y) << endl;
        LL t = K;
        while (t & (t - 1))
            t &= (t - 1);
        LL v = 2;
        t *= 2;
        if (t - 1 == K)
            v--;
        LL p = 0;
        while ((1LL << p) != t)
            p++;

        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)
        {
            cout << 2 << endl;
            return;
        }
        if (lx == t - 1)
            ans += 1;
        else if ((lx xor (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;
    }
}

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

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

    return 0;
}