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