#include<bits/stdc++.h>
#define fo(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define Ts template<typename Ty,typename... Ar>
#define Tp template<typename Ty>
#define ll long long
#define RS register
#define gc getchar
#define pc putchar
#define I inline
using namespace std;
Tp I Ty wmax(Ty a,Ty b){return a>=b? a:b;}
Tp I Ty wmin(Ty a,Ty b){return a<=b? a:b;}
namespace WrongIO
{
	Tp I void read(Ty &x){x=0;Ty opt=1;char c=gc();while(!isdigit(c)&&c!='-')c=gc();if(c=='-')opt=-1,c=gc();while(isdigit(c))x=(x<<3)+(x<<1),x+=c-'0',c=gc();x*=opt;return;}
	Tp I void write(Ty x){short OI_USE[50],OI_top=0;if(x<=0) if(x==0)pc('0');else pc('-'),x*=-1;while(x)OI_USE[++OI_top]=x%10,x/=10;while(OI_top--)pc(OI_USE[OI_top+1]+'0');return;}
    I void writec(char c[]){int len=strlen(c);for(int i=0;i<len;i++)pc(c[i]);}
    I void writes(string s){int len=s.length();for(int i=0;i<len;i++)pc(s[i]);}
    I void readc(char &c,int l,int r){c=gc(); while(c!=EOF&&(c<l||c>r)) c=gc();}
    I void readc(char &c,char val){c=gc();while(c!=EOF&&c!=val) c=gc();}
    I void readc(char val){char c;c=gc();while(c!=EOF&&c!=val) c=gc();}
    I void readls(string &s){char c=gc();while(c!='\n') s.push_back(c),c=gc();}
    Ts I void read(Ty &x,Ar &...y) {read(x),read(y...);}
} using namespace WrongIO;
__int128 T;
int main(){
	read(T);
	for(__int128 o=1;o<=T;o++)
	{
		__int128 a,b,p;
		read(a,b,p); if(a>b) swap(a,b);
		if(a==b)
		{
			write(0);pc('\n');continue;
		}
		if(p==0)
		{
			write(b-a);pc('\n');continue;
		}

		__int128 cs=__lg((unsigned ll)p)+1,ans=0,ans2=b-a,ans3=1152921504606846975;
		
		if(((b>>cs)<<cs)-((a>>cs)<<cs)==0)
		{	
			if((a^b)<=p) ans3=1;
			else ans3=2;
		}
		if(p==(__int128)pow(2,cs)-1)
		{
			if(a-((a>>cs)<<cs)==(__int128)pow((__int128)2,cs)-1) ans=1,a+=1;
			else if((1<<cs)-1-(a-((a>>cs)<<cs))>p) ans+=3,a=((a>>cs)+1<<cs);
			else ans+=2,a=((a>>cs)+1<<cs);
			__int128 shang=(b-a)/(ll)(pow((__int128)2,cs));
			ans+=shang*2; ans+=1; a=a+(__int128)pow(2,cs)*shang;
			if(b-a>p) ans+=1;
			if(b-a==0) ans-=1; 
		}
		else
		{
			if(a-((a>>cs)<<cs)==(__int128)pow((__int128)2,cs)-1) ans=1,a+=1;
			else if((1<<cs)-1-(a-((a>>cs)<<cs))>p) ans+=3,a=((a>>cs)+1<<cs);
			else ans+=2,a=((a>>cs)+1<<cs);
			__int128 shang=(b-a)/(ll)(pow((__int128)2,cs));
			ans+=shang*3; ans+=1; a=a+(__int128)pow(2,cs)*shang;
			if(b-a>p) ans+=1;
			if(b-a==0) ans-=1; 
		}
		ans2=wmin(ans2,ans3);
		write(wmin(ans,ans2)),pc('\n');
	}
	
}

answer.code: In function ‘int main()’:
answer.code:48:36: error: call of overloaded ‘pow(int, __int128&)’ is ambiguous
   48 |                 if(p==(__int128)pow(2,cs)-1)
      |                                 ~~~^~~~~~
In file included from /usr/include/features.h:461,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/c++config.h:586,
                 from /usr/include/c++/11/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from answer.code:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:140:1: note: candidate: ‘double pow(double, double)’
  140 | __MATHCALL_VEC (pow,, (_Mdouble_ __x, _Mdouble_ __y));
      | ^~~~~~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/cmath:392:3: note: candidate: ‘constexpr long double std::pow(long double, long double)’
  392 |   pow(long double __x, long double __y)
      |   ^~~
/usr/include/c++/11/cmath:388:3: note: candidate: ‘constexpr float std::pow(float, float)’
  388 |   pow(float __x, float __y)
      |   ^~~
answer.code:50:58: error: call of overloaded ‘pow(__int128, __int128&)’ is ambiguous
   50 |                         if(a-((a>>cs)<<cs)==(__int128)pow((__int128)2,cs)-1) ans=1,a+=1;
      |                                                       ~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/features.h:461,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/c++config.h:586,
                 from /usr/include/c++/11/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from answer.code:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:140:1: note: candidate: ‘double pow(double, double)’
  140 | __MATHCALL_VEC (pow,, (_Mdouble_ __x, _Mdouble_ __y));
      | ^~~~~~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/cmath:392:3: note: candidate: ‘constexpr long double std::pow(long double, long double)’
  392 |   pow(long double __x, long double __y)
      |   ^~~
/usr/include/c++/11/cmath:388:3: note: candidate: ‘constexpr float std::pow(float, float)’
  388 |   pow(float __x, float __y)
      |   ^~~
answer.code:53:54: error: call of overloaded ‘pow(__int128, __int128&)’ is ambiguous
   53 |                         __int128 shang=(b-a)/(ll)(pow((__int128)2,cs));
      |                                                   ~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/features.h:461,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/c++config.h:586,
                 from /usr/include/c++/11/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from answer.code:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:140:1: note: candidate: ‘double pow(double, double)’
  140 | __MATHCALL_VEC (pow,, (_Mdouble_ __x, _Mdouble_ __y));
      | ^~~~~~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/cmath:392:3: note: candidate: ‘constexpr long double std::pow(long double, long double)’
  392 |   pow(long double __x, long double __y)
      |   ^~~
/usr/include/c++/11/cmath:388:3: note: candidate: ‘constexpr float std::pow(float, float)’
  388 |   pow(float __x, float __y)
      |   ^~~
answer.code:54:64: error: call of overloaded ‘pow(int, __int128&)’ is ambiguous
   54 |                         ans+=shang*2; ans+=1; a=a+(__int128)pow(2,cs)*shang;
      |                                                             ~~~^~~~~~
In file included from /usr/include/features.h:461,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/c++config.h:586,
                 from /usr/include/c++/11/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from answer.code:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:140:1: note: candidate: ‘double pow(double, double)’
  140 | __MATHCALL_VEC (pow,, (_Mdouble_ __x, _Mdouble_ __y));
      | ^~~~~~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/cmath:392:3: note: candidate: ‘constexpr long double std::pow(long double, long double)’
  392 |   pow(long double __x, long double __y)
      |   ^~~
/usr/include/c++/11/cmath:388:3: note: candidate: ‘constexpr float std::pow(float, float)’
  388 |   pow(float __x, float __y)
      |   ^~~
answer.code:60:58: error: call of overloaded ‘pow(__int1...