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