# baby-step-giant-step
# (a**k)%mod=1となる最小のkを返す
def bsgs(a,mod):
  c=int(mod**0.5)+1
  d={}
  # baby-step
  now=1
  for i in range(c):
    d[now]=i
    now*=a
    now%=n
    if now==1:return i+1
  # giant-step
  now=1
  gs=pow(a,c,n)
  for i in range(c):
    pre=now
    now*=gs
    now%=n
    if now in d:return (i+1)*c-d[now]

# now=1からはじめ、以下を繰り返す。
# ・now%=n
# ・now*=10
# 過去に一度出たnowが再び出たらそこから循環する。nowの取りうる値は0~n-1なので循環は高々n個から成る。
# 10**k=1 (mod n)となるkで循環する
# baby-step-giant-step
if __name__=='__main__':
  t=int(input())
  cases=[int(input()) for _ in range(t)]
  for n in cases:
    retb=bsgs(10,n)
    print(retb)