Bittijono

def main():
    import math
    amount = int(input(""))
    bitit = [0, 1]

    for i in xrange(amount):
        luku = int(input(""))

        while (luku > 2):
            length = int(math.pow(2, math.ceil(math.log(luku, 2))))
            luku -= length/4
            if (luku > length/2):
                luku -= length/2

        print bitit[luku - 1]

main()

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED