#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll x, y, k;
void solve()
{
    scanf("%lld %lld %lld", &x, &y, &k);
    if (x == y)
    {
        puts("0");
        return;
    }
    if (k <= 1)
    {
        printf("%lld\n", abs(x - y));
        return;
    }
    if ((x ^ y) <= k)
    {
        puts("1");
        return;
    }
    int L = 0;
    while (k >> L)
        L++;
    int c = 2 - (k + 1 >> L);
    ll ans = 0;
    if (x < y)
        swap(x, y);
    if (x > y)
    {
        ll hx = x >> L, hy = y >> L;
        ll lx = x & (1ll << L) - 1, ly = y & (1ll << L) - 1;
        if (hx == hy)
        {
            ll rr = min(abs(x - y), 2LL);
            cout << rr << '\n';
            return;
        }
        if (!lx)
        {
            hx--;
            ans++;
            lx = (1ll << L) - 1;
        }
        else if (lx <= k)
        {
            hx--;
            ans += 2;
            lx = (1ll << L) - 1;
        }
        else
        {
            hx--;
            ans += c + 1;
            lx = (1ll << L) - 1;
        }
        if (hx == hy)
        {
            if (lx != ly)
            {
                if ((lx ^ ly) <= k)
                    ans++;
                else
                    ans += 2;
            }
            printf("%lld\n", ans);
            return;
        }
        ans += (hx - hy) * (c + 1);
        lx = (1ll << L) - 1;
        if (lx != ly)
        {
            if ((lx ^ ly) <= k)
                ans++;
            else
                ans += 2;
        }
    }
    printf("%lld\n", ans);
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
        solve();
    return 0;
}