#include <bits/stdc++.h>
using namespace std;
using LL=long long;
LL x,y,k;
LL solve()
{
    cin >>x >>y >>k;
    if(x == y) return 0;
    if(x >y) {
        int cnt = 0;
        LL t = 1, num = 0;
        if((k + 1&k) == 0) cnt = 2;
        else cnt = 3;
        for(int i = k;i;i>>=1) t<<=1,num++;
        LL s = (x>>num)-(y>>num);
        if(s == 0) {
            if((x^y)<=k) return 1;
            else return 2;
        }
        LL ans = 0;
        if((x&(t-1)) == 0) ans = 0;
        else if((x&(t-1))<=k) ans = 1;
        else ans = 2;
        ans += s * cnt - cnt + 1;
        if(((t-1&y)^(t-1))==0) return ans;
        if(((t-1&y)^(t-1))<=k) return ans + 1;
        return ans + 2;
    }
    int cnt = 0;
    if((k+1&k)==0) cnt=2;
    else cnt = 3;
    LL t = 1, num = 0;
    for(int i = k; i; i >>= 1) t<<=1,num++;
    LL s =(y>>num)-(x>>num);
    if(s == 0) {
        if((x^y)<=k) return 1;
        else return 2;
    }
    LL ans = 0;
    if((x&(t-1)^(t-1))==0) ans = 0;
    else if((x&(t-1)^(t-1))<=k) ans = 1;
    else ans = 2;
    ans += s *cnt - cnt +1;
    if((t-1&y)==0) return ans;
    if((t-1&y)<=k) return ans + 1;
    return ans + 2;


}
int main()

{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int T;
    for (cin>>T;T--;)
    {
        LL ans = solve();
        cout<<min(ans,max(x,y) - min(x,y))<<"\n";
    }
    return 0;
}