import java.util.*; public class _474 { public static void main(String[] args) { new _474().solve(); } void solve() { precalc(); try (final Scanner in = new Scanner(System.in)) { int T = in.nextInt(); while (T-- > 0) { int A = in.nextInt(); int B = in.nextInt(); int C = in.nextInt(); System.out.println(solve(A, B, C)); } } } final int mod = 2<<20; final long[] factFactor2 = new long[mod]; final long[] factMod1048576 = new long[mod]; void precalc() { factMod1048576[0] = 1; for (int i = 1; i < mod; i++) { int j, factor2 = 0; for (j = i; j % 2 == 0; j /= 2) factor2++; factMod1048576[i] = factMod1048576[i-1] * j % mod; factFactor2[i] = factFactor2[i-1] + factor2; } } int solve(int A, int B, int C) { if (C % 2 == 0) { return 0; } long[] cHb = H(C, B); long bit = ((C * cHb[1] % mod) << Math.min(32, cHb[0])) % mod + A - 1; // https://hermes-ir.lib.hit-u.ac.jp/rs/bitstream/10086/9464/1/HNshizen0001400750.pdf // 定理8より return (bit & A) == A ? 1 : 0; } long[] H(int n, int r) { long factor2 = factFactor2[n+r-1] - factFactor2[r] - factFactor2[n-1]; long val = factMod1048576[n+r-1] * modInverse(factMod1048576[r], mod) % mod * modInverse(factMod1048576[n-1], mod) % mod; return new long[]{ factor2, val, }; } static long modInverse(final long n, final long m) { final long[] res = extGcd(n, m); if (res[2] != 1) { dump(n, m, res); throw new RuntimeException(); } return (m + res[0]) % m; } static long[] extGcd(final long a, final long b) { if (b == 0) { return new long[] { 1, 0, a }; } final long[] res = extGcd(b, a % b); long y = res[0]; final long x = res[1]; y -= (a / b) * x; res[0] = x; res[1] = y; return res; } // for debug static void dump(Object... o) { System.err.println(Arrays.deepToString(o)); } }