package yukicoder; import java.util.*; public class Q474 { static class Int { long v = 0; long c = 0; public Int(long n) { while (n % 2 == 0) { n /= 2; ++c; } this.v = n; } public Int() { } Int mul(Int o) { Int i = new Int(); i.c = this.c + o.c; i.v = this.v * o.v % mod; return i; } Int divide(Int o) { Int i = new Int(); i.c = this.c - o.c; i.v = this.v * pow(o.v, mod / 2 - 1) % mod; return i; } long toLong() { long v = 1l << c; v = (v * this.v) % mod; return v; } } final static long mod = 1 << 20; public static void main(String[] args) { Int[] fac = new Int[2000001]; fac[0] = new Int(1); for (int i = 1; i < fac.length; ++i) { fac[i] = fac[i - 1].mul(new Int(i)); } Scanner sc = new Scanner(System.in); int T = sc.nextInt(); StringBuilder sb = new StringBuilder(); while (T-- > 0) { int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); if (c % 2 == 0) { System.out.println("0"); continue; } Int x = (new Int(c)).mul(fac[c + b - 1]).divide(fac[b]).divide(fac[c - 1]); if (((x.toLong() + a - 1) & a) == a) { sb.append("1\n"); } else { sb.append("0\n"); } } System.out.println(sb); } static long pow(long a, long n) { long ret = 1; for (; n > 0; n >>= 1, a = (a * a) % mod) { if (n % 2 == 1) ret = (ret * a) % mod; } return ret; } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }