#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
inline int qtop (long long x) {
	int t;
	while (x) {
		t++;
		x >>= 1;
	}
	return t;
}
int main () {
	int T;
	scanf("%d", &T);
	while (T--) {
		LL x, y, k;
		scanf("%lld%lld%lld", &x, &y, &k);
		int topk = qtop(k);
		if (x > y)
			swap(x, y);
		LL ans = y - x, maxn = (1ll<<topk) - 1;
		if (k <= 1) {
			printf("%lld\n", ans);
			continue;
		}
		
		if ((x^y) <= k) {
			printf("%lld\n", min(ans, 1ll));
			continue;
		}else if ((x^y) <= maxn) {
			printf("%lld\n", min(ans, 2ll));
			continue;
		}
		
		LL t = ((x&maxn) == maxn ? 1 : (((x>>topk<<topk ^ x ^ maxn) <= k ? 2: 3)));
		t += (k == maxn ? 2 : 3) * ((y>>topk) - (x>>topk) - 1);
		if (y&maxn)
			t += ((y&maxn) <= k ? 1 : 2);
		printf("%lld\n", min(ans, t));
	}
	return 0;
}