#include <bits/stdc++.h>
#define LL long long
LL x,y,k;
inline int getans(LL x){
    if(x == 0) return 0;
    if(x <= k) return 1;
    else return 2;
}
inline int getmax(LL x){
    int res = 0;
    while(x) res ++,x >>= 1;
    return res;
}
int main()
{

    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%lld",&x,&y,&k);
        if(k <= 1) printf("%lld\n",std::abs(x - y));
        else{
            LL tmp = x ^ y;
            int mk = getmax(k);
            int mt = getmax(tmp);
            if(mt <= mk) printf("%lld\n",getans(tmp));
            else{
                if(x < y){
                    LL ans = 0;
                    LL xlastk = x & ((1ll << mk) - 1);
                    ans += getans(((1ll << mk) - 1) ^ xlastk) + 1;
                    ans += 1ll * ((y >> mk) - (x >> mk) - 1) * (getans((1ll << mk) - 1) + 1);
                    ans += getans(y & ((1ll << mk) - 1));
                    printf("%lld\n",ans);
                }
                else{
                    LL ans = 0;
                    LL xlastk = x & ((1ll << mk) - 1);
                    ans += getans(xlastk) + 1;
                    ans += 1ll * ((x >> mk) - (y >> mk) - 1) * (getans((1ll << mk) - 1) + 1);
                    ans += getans(y & ((1ll << mk) - 1) ^ ((1ll << mk) - 1));
                    printf("%lld\n",ans);
                }

            }
        }
    }
    return 0;
}