Q=int(input())
for _ in range(Q):
  N=int(input())
  result=1
  for k in range(32):
    if not (2*(N-1)>>k)&1:
      if ((N-1)>>k)&1:
        result=0
  print(result)