/*********************************************************************
    程序名: 
    版权: 
    作者: 
    日期: 2024-01-12 17:48 
    说明: 
*********************************************************************/
#include<bits/stdc++.h>
using namespace std;
long long a, b, k, ah, bh, ans, mask, tmpk;
void solve()
{
	cin>>a>>b>>k;
	if(a<b)swap(a, b);
	if(a==b)
	{
		cout<<0<<endl;
		return ;
	}
	if(k<=1ll)
	{
		cout<<(a-b)<<endl;
		return;
	}
	bool flag = false;
	for(int i = 0;i < 63;i ++)
	{
		if(k == ((1ll<<i)-1ll))flag = true;
	}
	int bitcount=0;
	tmpk = k;
	while(tmpk)++bitcount,tmpk>>=1;
	ah=a>>bitcount,bh=b>>bitcount;
	if(ah == bh)
	{
		if((a^b) == k)cout<<1<<endl;
		else cout<<min(2ll, a-b)<<endl;
		return ;
	}
	ans=0;
	mask=(1ll<<bitcount)-1ll;
	if((a&mask)==0)ans+=0;
	else if((a&mask)>k)ans+=min(2ll, a&mask);
	else ++ans;
	ans+=(ah-bh)+(ah-bh-1ll)*(flag?1ll:2ll);
	if((b&mask)==mask)ans+=0;
	else if((mask^(b&mask))<= k)ans ++;
	else ans += min(2ll, mask-(b&mask));
	cout<<ans<<endl;
	
}
int T;
int main() {
	 cin>>T;
	while(T --)solve();
	return 0;
}