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

template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vc<int>;

#define int ll

template <class F>
struct ycr {
	F f;
	
	template <class T>
	explicit ycr(T&& f_) : f(forward<T>(f_)) {}

	template <class... Args>
	decltype(auto) operator()(Args&&... args) {
		return f(ref(*this), forward<Args>(args)...);
	}
};
template <class F>
decltype(auto) yc(F&& f) {
	return ycr<decay_t<F>>(forward<F>(f));
}

signed main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);
	int T;
	cin>>T;
	int x,y,k;
	while(T--)
	{
		cin>>x>>y>>k;
		if(x>y) swap(x,y);
		if(k==0)
		{
			cout<<y-x<<"\n";
			continue;
		}
		if(x==y)
		{
			cout<<"0"<<"\n";
			continue;
		}
		int now=1;
		while(now<=k) now*=2;
		if(k!=now-1)
		{
			int w=x^y;
			if(w<=k)
			{
				cout<<"1"<<"\n";
				continue;
			}
			int nxt=(x+now-1)/now*now;
			if(y<nxt)
			{
				cout<<"2"<<"\n";
				continue;
			}
			int ans=0;
			if(nxt!=x)
			{
				if(nxt-1==x) x++, ans++;
				else if(((nxt-1)^x)<=k) ans+=2, x=nxt;
				else ans+=3, x=nxt;
			}
			int res=(y-x)/now;
			ans+=res*3;
			x+=res*now;
			if(x!=y)
			{
				if((x^y)<=k) ans++;
				else ans+=2;
			} 
			cout<<ans<<"\n";
		}
		else
		{
			int w=x^y;
			if(w<=k)
			{
				cout<<"1"<<"\n";
				continue;
			}
			int nxt=(x+now-1)/now*now;
			if(y<nxt)
			{
				cout<<"2"<<"\n";
				continue;
			}
			int ans=0;
			if(nxt!=x)
			{
				if(nxt-1==x) x++, ans++;
				else if(((nxt-1)^x)<=k) ans+=2, x=nxt;
				else ans+=3, x=nxt;
			}
			int res=(y-x)/now;
			ans+=res*2;
			x+=res*now;
			if(x!=y)
			{
				if((x^y)<=k) ans++;
				else ans+=2;
			} 
			cout<<ans<<"\n";
		}
	}
}