Bittijono

import math
 
def getBitti(luku):
    if (luku > 4):
        length = math.pow(2, math.ceil(math.log(luku, 2)))
        if (luku > (length/4) * 3):
            return getBitti(luku - ((length/4) * 3))
        else:
            return getBitti(luku - (length/4))
    if (luku == 1):
        return 0
    if (luku == 2):
        return 1
    if (luku == 3):
        return 1
    if (luku == 4):
        return 0
 
 
def main():
    amount = int(input(""))
 
    for i in xrange(amount):
        print getBitti(int(input("")))
 
main()

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED