Bittijono

from math import pow
n = int(input())
l = 0
while l != n:
    a = int(input())
    e = 0
    s = 0
    while True:
        while s != 1:
            #print(str(a)+"LUKU")
            if a <= 1:
                s = 1
                break
            elif a ==1:
                s = 1
                break
            elif a == 2:
                s = 1
                break
            elif a <= pow(2,2) :
                a = a - 2
                e += 1
            elif a <= pow(2,3):
                a = a - pow(2,2)
                e += 1
            elif a <= pow(2,4):
                a = a - pow(2,3)
                e += 1
            elif a <= pow(2,5):
                a = a - pow(2,4)
                e += 1
            elif a <= pow(2,6):
                a = a - pow(2,5)
                e += 1
            elif a <= pow(2,7):
                a = a - pow(2,6)
                e += 1
            elif a <= pow(2,8):
                a = a - pow(2,7)
                e += 1
            elif a <= pow(2,9):
                a = a - pow(2,8)
                e += 1
            elif a <= pow(2,10):
                a = a - pow(2,9)
                e += 1
            elif a <= pow(2,11):
                a = a - pow(2,10)
                e += 1
            elif a <= pow(2,12):
                a = a - pow(2,11)
                e += 1
            elif a <= pow(2,13):
                a = a - pow(2,12)
                e += 1
            elif a <= pow(2,14):
                a = a - pow(2,13)
                e += 1
            elif a <= pow(2,15):
                a = a - pow(2,14)
                e += 1
            elif a <= pow(2,16):
                a = a - pow(2,15)
                e += 1
            elif a <= pow(2,17):
                a = a - pow(2,16)
                e += 1
            elif a <= pow(2,18):
                a = a - pow(2,17)
                e += 1
            elif a <= pow(2,19):
                a = a - pow(2,18)
                e += 1
            elif a <= pow(2,20):
                a = a - pow(2,19)
                e += 1
            elif a <= pow(2,21):
                a = a - pow(2,20)
                e += 1
            elif a <= pow(2,22):
                a = a - pow(2,21)
                e += 1
            elif a <= pow(2,23):
                a = a - pow(2,22)
                e += 1
            elif a <= pow(2,24):
                a = a - pow(2,23)
                e += 1
            elif a <= pow(2,25):
                a = a - pow(2,24)
                e += 1
            elif a <= pow(2,26):
                a = a - pow(2,25)
                e += 1
            elif a <= pow(2,27):
                a = a - pow(2,26)
                e += 1
            elif a <= pow(2,28):
                a = a - pow(2,27)
                e += 1
            elif a <= pow(2,29):
                a = a - pow(2,28)
                e += 1
            elif a <= pow(2,30):
                a = a - pow(2,29)
                e += 1
            elif a <= pow(2,31):
                a = a - pow(2,30)
                e += 1
            elif a <= pow(2,32):
                a = a - pow(2,31)
                e += 1
            elif a <= pow(2,33):
                a = a - pow(2,32)
                e += 1
            elif a <= pow(2,34):
                a = a - pow(2,33)
                e += 1
            elif a <= pow(2,35):
                a = a - pow(2,34)
                e += 1
            elif a <= pow(2,36):
                a = a - pow(2,35)
                e += 1
            elif a <= pow(2,37):
                a = a - pow(2,36)
                e += 1
            elif a <= pow(2,38):
                a = a - pow(2,37)
                e += 1
            elif a <= pow(2,39):
                a = a - pow(2,38)
                e += 1
            elif a <= pow(2,40):
                a = a - pow(2,39)
                e += 1
            elif a <= pow(2,41):
                a = a - pow(2,40)
                e += 1
            elif a <= pow(2,42):
                a = a - pow(2,41)
                e += 1
            elif a <= pow(2,43):
                a = a - pow(2,42)
                e += 1
            elif a <= pow(2,44):
                a = a - pow(2,43)
                e += 1
            elif a <= pow(2,45):
                a = a - pow(2,44)
                e += 1
            elif a <= pow(2,46):
                a = a - pow(2,45)
                e += 1
            elif a <= pow(2,47):
                a = a - pow(2,46)
                e += 1
            elif a <= pow(2,48):
                a = a - pow(2,47)
                e += 1
            elif a <= pow(2,49):
                a = a - pow(2,48)
                e += 1
            elif a <= pow(2,50):
                a = a - pow(2,49)
                e += 1
            elif a <= pow(2,51):
                a = a - pow(2,50)
                e += 1
            elif a <= pow(2,52):
                a = a - pow(2,51)
                e += 1
            elif a <= pow(2,53):
                a = a - pow(2,52)
                e += 1
            elif a <= pow(2,54):
                a = a - pow(2,53)
                e += 1
            elif a <= pow(2,55):
                a = a - pow(2,54)
                e += 1
            elif a <= pow(2,56):
                a = a - pow(2,55)
                e += 1
            elif a <= pow(2,57):
                a = a - pow(2,56)
                e += 1
            elif a <= pow(2,58):
                a = a - pow(2,57)
                e += 1
            elif a <= pow(2,59):
                a = a - pow(2,58)
                e += 1
            elif a <= pow(2,60):
                a = a - pow(2,59)
                e += 1
 
        if a == 2 and e%2 == 0:
            #print(e)
            a = 1
            l += 1
            #print(l)
            print(a)
            break
        elif a ==1 and e%2 != 0:
            #print(e)
            a = 1
            l += 1
            #print(l)
            print(a)
            break
        elif a == 2 and e%2 != 0:
            a = 0
            l +=1
            print(a)
            break
        elif a == 1 and e%2 == 0:
            a = 0
            l +=1
            print(a)
            break
        break

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED