require "prime"
T = gets.to_i
T.times do
    N = gets.to_i
    n = N
    n /= 2 while n % 2 == 0
    n /= 5 while n % 5 == 0
    len = 1
    repnov = 9 % n
    until repnov == 0
        repnov = (repnov * 10 + 9) % n
        len += 1
    end
    puts len
end