#include <cstdio>
#define rep(i, d, u) for(int i = d; i <= u; ++i)
#define cep(n) while(n--)
int ured() {
	int re = 0;
	char ch;
	do {
		ch = getchar();
	} while('9' < ch || ch < '0');
	do {
		re = re * 10 + (ch ^ '0');
	} while('0' <= (ch = getchar()) && ch <= '9');
	return re;
}
long long lred() {
	long long re = 0;
	char ch;
	do {
		ch = getchar();
	} while('9' < ch || ch < '0');
	do {
		re = re * 10 + (ch ^ '0');
	} while('0' <= (ch = getchar()) && ch <= '9');
	return re;
}
void lwit(long long da) {
	int ch[21], cn = 0;
	do {
		ch[++cn] = da - da / 10 * 10;
	} while(da /= 10);
	do {
		putchar('0' ^ ch[cn]);
	} while(--cn);
}
void swap(long long &le, long long &ri) {
	long long tp = le;
	le = ri, ri = tp;
}
int t, dpos, ddat;
long long x, y, s, rans;
int main() {
	t = ured();
	cep(t) {
		x = lred(), y = lred(), s = lred();
		if(x == y) {
			puts("0");
			continue;
		} else if(x > y) {
			swap(x, y);
		}
		if(s > 1) {
			dpos = 64 - __builtin_clzll(s);
			if((x ^ y) >> dpos) {
				if(s == (1ll << dpos) - 1) {
					rans = (y >> dpos) - (x >> dpos) - 1 << 1;
				} else {
					rans = ((y >> dpos) - (x >> dpos) - 1) * 3;
				}
				++rans;
				if(ddat = x & (1ll << dpos) - 1 ^ (1ll << dpos) - 1) {
					if(ddat <= s) {
						++rans;
					} else {
						rans += 2;
					}
				}
				if(ddat = y & (1ll << dpos) - 1) {
					if(ddat <= s) {
						++rans;
					} else {
						rans += 2;
					}
				}
				lwit(rans), putchar('\n');
			} else if((x ^ y) <= s || y == x + 1) {
				puts("1");
			} else {
				puts("2");
			}
		} else {
			lwit(y - x), putchar('\n');
		}
	}
	return 0;
}