Bittijono

from math import log2, pow

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:
            if k == 1:
                l = 1
            #print(k)
            j = float(k)
            c = log2(k)
            #print(c)
            if round(c) > c:
                c = round(c)-1
            if pow(2,c) == k:
                c = c - 1
            else:
                c = round(c)
            p = pow(2,c)

            #print(p)
            k = int(k-p)
            e += 1
            d += 1
            break
            #
            #     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: WRONG ANSWER

Test 2

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED