Bittijono

def powOf2(x):
    i = 1
    while 2**i < x:
        i = i + 1
    return i-1

def bitAt(x):
    if x == 0:
        return False
    elif x == 1:
        return True
    elif x == 2:
        return True
    else:
        return not bitAt(x-2**powOf2(x+1))

for x in range(int(raw_input())):
    print(str(int(bitAt(int(raw_input())-1))))

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED