#include 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; }