Bittijono

import math

def getBitti(luku):
    bitit = [0, 1]

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

    print bitit[luku - 1]

def main():
    amount = int(input(""))

    for i in xrange(amount):
        getBitti(int(input("")))

main()

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED