#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
typedef long long LL;
using namespace std;
inline LL read() {
    LL num = 0 ,f = 1; char c = getchar();
    while (!isdigit(c)) f = c == '-' ? -1 : f ,c = getchar();
    while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
    return num * f;
}
LL x ,y ,k;
inline void fuling_solve() {
    x = read() ,y = read() ,k = read();
    if (k == 0) return printf("%lld\n" ,abs(x - y)) ,void();
    if (x > y) swap(x ,y);
    if ((x ^ y) <= k) return printf("%lld\n" ,1ll) ,void();
    int fir = 0;
    for (int i = 60; i >= 0; i--) if (k >> i & 1) {fir = i; break;}
    LL res = 1 ,qs = 0;
    for (int i = fir; i >= 0; i--) if (!(x >> i & 1)) qs |= 1ll << i;
    if (qs > 0 && qs <= k) res++;
    else if (qs > k) res += 2;
    x |= qs;
    if (x >= y) return puts("2") ,void();
    x++;
    LL q = (y - x) / (2ll << fir);
    res += q * (k == ((2ll << fir) - 1) ? 2 : 3);
    x += q * (2ll << fir);
    if (x == y) printf("%lld\n" ,res);
    else if ((x ^ y) <= k) printf("%lld\n" ,res + 1);
    else printf("%lld\n" ,res + 2);
}
signed main() {
    int t = read();
    while (t--) fuling_solve();
    return 0;
}