def solve():
  def inv(n):
    ret = n
    for i in range(5):
      ret = ret * (2 - ret * n % mod) % mod
    return ret

  def binom(n, m):
    ret = facts[n] * inv(facts[m] * facts[n - m] % mod) % mod
    v = vs[n] - vs[m] - vs[n - m]
    ret = (ret << v) % mod
    return ret

  def ctz(n):
    return (n & -n).bit_length() - 1

  def calc(A, B, C):
    if C % 2 == 0:
      return 0
    x = (C * binom(C - 1 + B, B) + A - 1) % mod
    return 1 if (x & A) == A else 0

  N = 2 * 10 ** 6 + 20
  mod = 2 ** 30

  vs = [0] + [ctz(i) for i in range(1, N)]
  facts = [1] * N
  for i in range(1, N):
    facts[i] = facts[i - 1] * (i >> vs[i])  % mod
  for i in range(1, N):
    vs[i] += vs[i - 1]

  import sys
  input = sys.stdin.readline
  T = int(input())
  results = []
  for _ in range(T):
    a, b, c = map(int, input().split())
    results += [calc(a, b, c)]
  print("\n".join([`ans` for ans in results]))

solve()