#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx;
#define For(i,x,y,...) for(int i=x,##__VA_ARGS__;i<=(y);++i)
#define rFor(i,x,y,...) for(int i=x,##__VA_ARGS__;i>=(y);--i)
#define Rep(i,x,y,...) for(int i=x,##__VA_ARGS__;i<(y);++i)
#define pb emplace_back
#define sz(a) int((a).size())
#define all(a) begin(a),end(a)
#define fi first
#define se second
typedef long long LL; typedef vector<int> Vi; typedef pair<int,int> Pii;
auto ckmax=[](auto &x,auto y) { return x<y ? x=y,true : false; };
auto ckmin=[](auto &x,auto y) { return y<x ? x=y,true : false; };
sfmt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r) { return uniform_int_distribution<>(l,r)(mt); }
template<typename T=int>T read() { T x; cin>>x; return x; }

const int mod = 998244353;
struct mint {
	int x; mint(int x=0):x(x<0?x+mod:x<mod?x:x-mod){}
	mint(LL y) { y%=mod, x=y<0?y+mod:y; }
	mint& operator += (const mint &y) { x=x+y.x<mod?x+y.x:x+y.x-mod; return *this; }
	mint& operator -= (const mint &y) { x=x<y.x?x-y.x+mod:x-y.x; return *this; }
	mint& operator *= (const mint &y) { x=1ll*x*y.x%mod; return *this; }
	friend mint operator + (mint x,const mint &y) { return x+=y; }
	friend mint operator - (mint x,const mint &y) { return x-=y; }
	friend mint operator * (mint x,const mint &y) { return x*=y; }
};	mint Pow(mint x,LL y=mod-2) { mint z(1);for(;y;y>>=1,x*=x)if(y&1)z*=x;return z; }

int k;
LL a,b,m,ri,ans;

void MAIN() {
	cin>>a>>b>>m;
	if( !m ) { cout<<abs(a-b)<<'\n'; return; }
	k = 63-__builtin_clzll(m), ri = (1ll<<k+1)-1;
	LL a0 = a>>k+1, b0 = b>>k+1, a1 = a & ri;
	if( a0 < b0 ) {
		LL x = a1 ^ ri;
		ans += !!x + (x>m) + 1;
		ans += (b0-a0-1) * ((m==ri?1:2) + 1);
		if( b &= ri ) {
			ans += b<=m ? 1 : 2;
		}
	} else if( a0 == b0 ) {
		ans += (a^b)<=m ? 1 : 2;
	} else {
		ans += !!a1 + (a1>m) + 1;
		ans += (a0-b0-1) * ((m==ri?1:2) + 1);
		if( b = (b & ri) ^ ri ) {
			ans += b<=m ? 1 : 2;
		}
	}
	cout<<ans<<'\n';
} signed main() {
#ifdef FT
	freopen("in","r",stdin); freopen("out","w",stdout);
#endif
	ios::sync_with_stdio(0);cin.tie(0);
	int lft=read(); while( lft-- ) {
		MAIN();
		ans = 0;
	}
	return 0;
}