Bittijono

import math, random, sys
global bitit
bitit = {}
bitit[1] = 0
bitit[2] = 1

def getBitti(luku):

    if luku not in bitit:
        # try:
        length = int(math.pow(2, math.ceil(math.log(luku, 2))))
        luku -= length/4
        if (luku > length/2):
            luku -= length/2
        bitti = getBitti(luku)
        bitit[luku] = bitti
        return getBitti(luku)
        # except ValueError:
        #     print luku
        #     sys.exit()

    return bitit[luku]

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

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

# def test(maara):
#     lista = [i + 1 for i in range(maara)]
#     #random.shuffle(lista)
#
#     for i in lista:
#         a = ""
#         a += str(i) + ": "
#         print a + str(getBitti(i))

main()
#test(100000)

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED