Help! TLE on 370, ONEZERO

I am new to python. Please tell me how to fix my code! Thank you very much!

spoj.pl/problems/ONEZERO/

t=int(raw_input())
while t:
    n=int(raw_input())
    if n==1:print 1
    else:
       a=dict([(1,1)])
       s=0;
       while True:
           b=dict()
           for i in a.keys(): 
               if (i*10)%n==0:
                   if s==0 or s>a[i]*10:s=a[i]*10
               if (i*10+1)%n==0:
                   if s==0 or s>a[i]*10+1:s=a[i]*10+1
               if not(b.has_key((i*10)%n)):
                   b.update([((i*10)%n,a[i]*10)])
               if not(b.has_key(i*10+1)):
                   b.update([((i*10+1)%n,a[i]*10+1)])       
           if s<>0: break;
           a=b
       print s   
    t-=1