/*

  0. Enough array size? Enough array size? Enough array size? Integer overflow?



  1. Think TWICE, Code ONCE!

  Are there any counterexamples to your algo?



  2. Be careful about the BOUNDARIES!

  N=1? P=1? Something about 0?



  3. Do not make STUPID MISTAKES!

  Time complexity? Memory usage? Precision error?

*/
#include <bits/stdc++.h>

using ullong = unsigned long long;
using ldouble = long double;
using llong = long long;
using uint = unsigned int;

const int MOD = 1e9 + 7;
const int N = 1e6 + 10;

int main(void)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

    int _;
    std::cin >> _;

#ifdef __AT_LOCAL__
    clock_t __start_time = clock();
#endif

    while (_--)
    {
        ullong x, y, k;
        std::cin >> x >> y >> k;

        if (x > y) std::swap(x, y);

        if (x == y or k <= 1)
        {
            std::cout << y - x << '\n';
            continue;
        }

        ullong value = !!k, top = 1;
        while (value < k) value = value << 1 | 1, top <<= 1;

        int ans = 0;
        if ((x & value) ^ (value))
        {
            ++ans;
            if (((x & value) ^ value) > k)
            {
                if ((x | top) < y)
                    ++ans;
            }
            x |= value;
        }

        while (x < y)
        {
            ++x; ++ans;
            if (x >= y) break;

            if ((x & value) ^ (value))
            {
                ++ans;
                if (((x & value) ^ value) > k)
                {
                    if ((x | top) < y)
                        ++ans;
                }
                x |= value;
            }
        }
        std::cout << ans << '\n';
    }

#ifdef __AT_LOCAL__
    std::cout << "Exit after " << clock() - __start_time << "ms as " << (clock() - __start_time) / 1000 << "s\n";
#endif

    return 0;
}