#include<bits/stdc++.h>
#define MAXN 500010
#define INF 1000000010
#define MOD 998244353
#define LL long long
#define LLL __int128_t
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
void Main(){
	LL x,y,k;cin>>x>>y>>k;
	if (x>y) swap(x,y);
	if (k<=1){
		cout<<y-x<<"\n";
		return ;
	}
	if (x==y){
		cout<<0<<"\n";
		return ;
	}
	if ((x^y)<=k){
		cout<<1<<"\n";
		return ;
	}
	int len=0;
	For(i,1,61){
		len=i; 
		if ((1LL<<len)>k) break;
	}
	LL base=(1LL<<len);
	if (x/base==y/base){
		cout<<2<<"\n";
		return ;
	}
	int step=1;
	if (k==(base-1)) step=2;
	else step=3;
	int ans=0;
	if (x%base==base-1) ans=1;
	else if (((base-1)^(x%base))<=k) ans=2;
	else ans=3;
	x=(x/base+1)*base;
	ans+=1LL*(y/base-x/base)*step;
	x=(y/base)*base;
	if (x==y);
	else if ((x^y)<=k) ans++;
	else ans+=2;
	cout<<min(ans,abs(y-x))<<"\n";
}
int main(){
	std::ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;cin>>T;
	while (T--) Main();
}
/*
8
4 5 0
5 8 3
9 2 6
15 28 5
97 47 8
164 275 38
114514 1919 810
0 1152921504606846975 1
*/

answer.code: In function ‘void Main()’:
answer.code:48:18: error: no matching function for call to ‘min(int&, long long int)’
   48 |         cout<<min(ans,abs(y-x))<<"\n";
      |               ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)’
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
answer.code:48:18: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
   48 |         cout<<min(ans,abs(y-x))<<"\n";
      |               ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)’
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
answer.code:48:18: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
   48 |         cout<<min(ans,abs(y-x))<<"\n";
      |               ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)’
 3449 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note:   template argument deduction/substitution failed:
answer.code:48:18: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
   48 |         cout<<min(ans,abs(y-x))<<"\n";
      |               ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)’
 3455 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note:   template argument deduction/substitution failed:
answer.code:48:18: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
   48 |         cout<<min(ans,abs(y-x))<<"\n";
      |               ~~~^~~~~~~~~~~~~~