T = int(input())
for i in range(T):
  N = int(input())
  while N%2 == 0:
      N = N//2
  while N%5 == 0:
      N = N//5
  d = 1
  if pow(10, d, N) != 0:
    while pow(10, d, N) != 1:
      d += 1
    print(d)
  else:
    print(1)