#include <bits/stdc++.h>

using namespace std;

const int MaxN = (int)2e5 + 10;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int bits[1 << 16];
int dp[32][32][32][2];
int cc[32];

int getBits(int x) {
	return bits[x >> 16] + bits[x & 65535];
}

int getWays(int bit, int aa, int bb, int carry) {
	if (bit == 0) {
		return aa == 0 && bb == 0 && carry == 0;
	}
	if (dp[bit][aa][bb][carry] != -1) {
		return dp[bit][aa][bb][carry];
	}
	int &res = (dp[bit][aa][bb][carry] = 0);
	for (int ncarry = 0; ncarry < 2; ++ncarry) {
		for (int ai_1 = 0; ai_1 < 2; ++ai_1) {
			if (aa >= ai_1) {
				for (int bi_1 = 0; bi_1 < 2; ++bi_1) {
					if (bb >= bi_1) {
						if ((ncarry + ai_1 + bi_1) / 2 == carry && 
							(ncarry + ai_1 + bi_1) % 2 == cc[bit - 1]) {
							res += getWays(bit - 1, aa - ai_1, bb - bi_1, ncarry);
						}
					}
				}
			}
		}
	}
	return res;
}

void solve() {
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	assert (1 <= a && a <= 1e9);
	assert (1 <= b && b <= 1e9);
	assert (1 <= c && c <= 1e9);
	assert (a + b == c);
	for (int i = 0; i < 31; ++i) {
		cc[i] = (c >> i) & 1;
	}
	memset(dp, -1, sizeof(dp));
	cout << getWays(31, getBits(a), getBits(b), 0) << "\n";
}

int main() {
//	freopen("input.txt", "w", stdout);
	srand(time(NULL));
	for (int i = 1; i < 1 << 16; ++i) {
		bits[i] = bits[i / 2] + (i & 1);
	}
	int t;
	scanf("%d", &t);
	while (t --> 0) {
		solve();
	}
	return 0;
}