#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ll long long
#define int long long

int len(int x){
    int cnt=0;
    while(x){
        cnt++;
        x/=2;
    }
    return cnt;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
         int x,y,k;
         cin>>x>>y>>k;
         if(k==0){
            cout<<abs(x-y)<<endl;
            continue;
         }
         if(abs(x-y)<=1){
            cout<<abs(x-y)<<endl;
            continue;
         }
         if(x>=y){
            swap(x,y);
         }
         int l1=len(x),l2=len(y),l3=len(k);
         int x1=(x>>l3),x2=x-(x1<<l3);
         int y1=(y>>l3),y2=y-(y1<<l3);
         int cha=y1-x1;
         if(cha==0){
            if((x2^y2)<=k){
                cout<<1<<endl;
            }
            else {
                cout<<2<<endl;
            }
            continue;
         }
         int ci=2;
         if(k==(1<<l3)-1){
            ci=1;
         }
         int zong=(cha-1)*(ci+1);
         if(y2==0){
            zong+=0;
         }
         else if(y2<=k){
            zong+=1;
         }
         else {
            zong+=2;
         }
         if(x2==((1<<l3)-1)){
            zong+=1;
         }
         else if((x2^((1<<l3)-1))<=k){
            zong+=2;
         }
         else {
            zong+=3;
         }
         cout<<zong<<endl;
    }
    return 0;
}