Bittijono

import math, random, sys

class Bittijono():
    def __init__(self):
        bitit = {}
        bitit[1] = 0
        bitit[2] = 1
        self.bitit = bitit
    def getBitti(self, luku):
        if luku not in self.bitit:
            length = int(math.pow(2, math.ceil(math.log(luku, 2))))
            luku -= length/4
            if (luku > length/2):
                luku -= length/2
            bitti = self.getBitti(luku)
            self.bitit[luku] = bitti
            return bitti

        return self.bitit[luku]

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

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

def test(maara):
    jono = Bittijono()
    lista = [(i + 1) * 1000000000 for i in range(maara)]

    for i in lista:
        a = ""
        a += str(i) + ": "
        print a + str(jono.getBitti(i))

main()
#test(100000)

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED