Bittijono

# import re
# import math
# a = 1
# d = 0
# b = 0
 
#print(lis)
# bitti = ["","0","1","1","0","1","0","0","1"]
 
# def kerroin(a):
#     a = 2*a
#     return a
 
 
 
n = int(input())
o = 0
while o != n:
    k = int(input())
    c = 1
    d = 1
    e = 1
    l = 0
    while True:
        if l == 1:
            if e % 2 == 0 and k == 1:
                k = 1
                print(int(k))
                l = 0
                o += 1
                #del lis[0]
                break
            if e% 2 != 0 and k == 1:
                k = 0
                print(int(k))
                o += 1
                l = 0
                #del lis[0]
                break
            if d % 2 == 0:
                k = 0
                print((k))
                #del lis[0]
                o +=  1
                l = 0
                break
 
            else:
                k = 1
                print(int(k))
                #del lis[0]
                o = o + 1
                l = 0
                break
        while True:
            c = c + c
            if k == 1:
                l = 1
                break
            if c > k:
                c = c/2
                k = k-c
                #print (k)
                d += 1
                e += 1
                c = 1
                break
            if c == k and c != 2:
                c = c/2
                k = k-c
                d += 1
                e += 1
                #print(k)
                c = 1
            if c == k and c == 2:
                l = 1
                break
 
 
        # k = int(lis[0])
        # while k > 4:
        #     while k > a:
        #         a = kerroin(a)
        #     if a > k:
        #         a = a/2
        #         #print(a)
        #         k = k-a
        #         a = 1
        #         b = b+1
        #
        #         #print(str(k) + "HEH")
        #     if k < 0:
        #         k = k+a
        #         k = k-2
        #         #print(str(k) + "HAH")
        #     if k == a:
        #         while a > 4:
        #
        #             a = a/2
        #             d = d+1
        #
        #             if a is 2 or 4:
        #                 k = a
        #     if d > 0:
        #         if d%2 == 0:
        #             k = 0
        #         else:
        #             k = 1
        #
        # if k < 5:
        #     if b%2 == 0:
        #         k = k
        #     else:
        #         k = k +4
        #     print(bitti[int(k)])
        #     #print(lis[0] +"arvo on " + bitti[int(k)])
        #     del lis[0]
        #     a = 1
        #     d = 0
        #     b = 0
 

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED