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

const int N = 1e6 + 5;

ll x, y, k;
int a[100], b[100], c[100];

void run(){
    cin>>x>>y>>k;
	if(x>y) swap(x,y);

	if(k<=1||x==y)
	{
		cout<<abs(x-y)<<"\n";
		return ;
	}
	
	if((x^y)<=k||x+1==y)
	{
		cout<<1<<"\n";
		return ;
	}

    ll cntx = 0, cnty = 0, cntk = 0;
    ll t = x;
    while (t) {
        a[++ cntx] = (t & 1);
        t >>= 1;
    }

    t = y;
    while (t) {
        b[++ cnty] = t & 1;
        t >>= 1;
    }

    bool ok = 0;
    t = k;
    while (t) {
        c[++ cntk] = t & 1;
        if (!c[cntk]) ok = 1;
        t >>= 1;
    }

    int cost = ok + 2;
    int lenx = cntx, lenk = cntk;
    while (++ cntx < cnty) a[cntx] = 0;
    while (++ cntk < cnty) c[cntk] = 0; 

    ll res = 0;
    for (int i = cnty; i > lenk; i -- ) {
        if (b[i] == 1) res += pow(2, i - lenk - 1) * cost;
        if (a[i] == 1) res -= pow(2, i - lenk - 1) * cost;
    }

    ll tmp = 1, sum = 0;
    for (int i = 1; i <= lenk; i ++ ) {
        if (!a[i]) sum += tmp;
        tmp <<= 1;
    }
    
    if (sum == 0) res = res - cost + 1;
    else if (sum <= k) res = res -cost + 2;

    tmp = 1, sum = 0;
    for (int i = 1; i <= lenk; i ++ )  {
        if (b[i]) sum += tmp;
        tmp <<= 1;
    }

    if (sum > k) res += 2;
    else res += sum != 0;

    cout << res << '\n';
    for (int i = 1; i <= cnty; i ++ ) a[i] = b[i] = c[i] = 0;
}    

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    int tcase = 1;
    cin>>tcase;
    while(tcase--) run();
}