from math import sqrt, floor



n = int(input())

for i in range(n):
    k = int(input())
    k -= 1

    t = floor(sqrt (2*k+2)-.5)
    a_k = 1 << t

    t = floor(sqrt(2*k+1)+.5)
    pos =  ( t*t + t - (k << 1) - 2) >> 1

    bit = (a_k >> pos & 1)
    print(bit, end=' ')