Mul

[eskay]

I have implemented Booth's algorithm for integer multiplication which runs in O(n)for a pair of i/p. But still I get tle
[code]t=input()
for i in range(t):
a=raw_input()
b=a.split()
x=int(b[0])
y=int(b[1])
prev=0
ans=0
c=1
while(y!=0):
pres=y&1

    if(prev==0):
        if(pres==1):
            ans=ans+c*x
    if(prev==1):
        if(pres==0):
            ans=ans-c*x

    prev=pres
    y=y/2
    c=c*2
if(prev==1):
    ans=ans-c*x   

   
ans=-ans
print ans
[/code]

please help