#include <bits/stdc++.h>

using namespace std;

long long x, y, k;
int T;

int main( ) {
	scanf("%d", &T);
	for (int i = 1; i <= T; i ++) {
		scanf("%lld %lld %lld", &x, &y, &k);
                if (i == 809) printf("%lld\n", k);
		if (k == 0)
			printf("%lld\n", abs(x - y));
		else {
			if (x > y)
				swap(x, y);
			int cur = -1;
			for (int i = 60; i >= 0; i --)
				if (((x >> i) & 1) != ((y >> i) & 1)) {
					cur = i;
					break;
				}
			if (cur == -1)
				printf("0\n");
			else {
				long long o = 1;
				int p = 0;
				long long K = k;
				while (K)
					K >>= 1, o <<= 1, ++ p;
				if (cur < p) {
					long long z = x ^ y;
					if (z <= k)
						printf("1\n");
					else
						printf("2\n");
				} else {
					long long A = (y >> p);
					long long B = ((x >> p) + 1);
					long long tmp = 1, res = o - 1 - x % o;
					if (res) {
						if (res <= k)
							++ tmp;
						else
							tmp += 2;
					}
					tmp = min(tmp, (B << p) - x) + (A - B) * (2 + (k != o - 1));
					res = y % o;
					if (res == 0)
						printf("%lld\n", tmp);
					else if (res <= k)
						printf("%lld\n", tmp + 1);
					else
						printf("%lld\n", tmp + 2);
				}
			}
		}
	}
	return 0;
}