Help! TLE on 370, ONEZERO

[gyz_sof]

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

[numerix]

I am new to python. Please tell me how to fix my code!

What has do be fixed? Is it a NZEC or WA or TLE?

[gyz_sof]

It's TLE.

[numerix]

1. Your algorithm is wrong.
2. If it were right, it would be by far too slow.
3. You need another approach ...