#include <bits/stdc++.h>

using namespace std;

signed main() {
    int T; scanf("%d", &T);
    while (T--) {
        long long x, y, z; scanf("%lld%lld%lld", &x, &y, &z);
        if (x == y) {
            puts("0");
            continue;
        }
        if (z <= 1) {
            printf("%lld\n", abs(x - y));
            continue;
        }
        if (x > y) swap(x, y);
        int k = 0;
        while ((1ll << k) <= z) ++k;
        if ((x >> k) == (y >> k)) {
            if (x + 1 == y || (x ^ y) <= z) puts("1");
            else puts("2");
        } else {
            long long e1 = (((x >> k) + 1) << k) - 1, e2 = ((y >> k) << k);
            long long res = (x == e1 ? 0 : (x + 1 == e1 || (x ^ e1) <= z ? 1 : 2)) + (y == e2 ? 0 : (y - 1 == e2 || (y ^ e2) <= z ? 1 : 2)) + 1;
            printf("%lld\n", res + ((e2 - 1 - e1) >> k) * (2 + (z != (1 << y) - 1)));
        }
    }
    return 0;
}