import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
import strutils
ImportExpand "cplib/math/euler_phi.nim" <=== "when not declared CPLIB_MATH_EULER_PHI:\n    const CPLIB_MATH_EULER_PHI* = 1\n    import sequtils\n    proc euler_phi*(n: int): int =\n        result = n\n        var n = n\n        for i in 2..<n:\n            if i+i > n:\n                break\n            if n mod i == 0:\n                result -= result div i\n                while n mod i == 0:\n                    n = n div i\n        if n > 1:\n            result -= result div n\n\n    proc euler_phi_list*(n: int): seq[int] =\n        result = (0..n).toSeq\n        for i in 2..n:\n            if result[i] == i:\n                for j in countup(i, n, i):\n                    result[j] = result[j] div i\n                    result[j] *= (i - 1)\n    discard\n"

ImportExpand "cplib/math/divisor.nim" <=== "when not declared CPLIB_MATH_DIVISOR:\n    const CPLIB_MATH_DIVISOR* = 1\n    import sequtils\n    import tables\n    import algorithm\n    #[ import cplib/math/primefactor ]#\n    when not declared CPLIB_MATH_PRIMEFACTOR:\n        const CPLIB_MATH_PRIMEFACTOR* = 1\n        #[ import cplib/math/inner_math ]#\n        when not declared CPLIB_MATH_INNER_MATH:\n            const CPLIB_MATH_INNER_MATH* = 1\n            proc mul*(a, b, m: int): int {.importcpp: \"(__int128)(#) * (#) % (#)\", nodecl.}\n            discard\n        #[ import cplib/math/isprime ]#\n        when not declared CPLIB_MATH_ISPRIME:\n            const CPLIB_MATH_ISPRIME* = 1\n            #[ import cplib/math/powmod ]#\n            when not declared CPLIB_MATH_POWMOD:\n                const CPLIB_MATH_POWMOD* = 1\n                #[ import cplib/math/inner_math ]#\n                proc powmod*(a, n, m: int): int =\n                    var\n                        rev = 1\n                        a = a\n                        n = n\n                    while n > 0:\n                        if n mod 2 != 0: rev = mul(rev, a, m)\n                        if n > 1: a = mul(a, a, m)\n                        n = n shr 1\n                    return rev\n                discard\n            proc isprime*(N: int): bool =\n                let bases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]\n                if N == 2:\n                    return true\n                if N < 2 or (N and 1) == 0:\n                    return false\n                let N1 = N-1\n                var d = N1\n                var s = 0\n                while (d and 1) == 0:\n                    d = d shr 1\n                    s += 1\n                for a in bases:\n                    var t: int\n                    if a mod N == 0:\n                        continue\n                    t = powmod(a, d, N)\n                    if t == 1 or t == N1:\n                        continue\n                    block test:\n                        for _ in 0..<(s-1):\n                            t = powmod(t, 2, N)\n                            if t == N1:\n                                break test\n                        return false\n                return true\n            discard\n        import random\n        import std/math\n        import algorithm\n        import tables\n    \n        randomize()\n        proc find_factor(n: int): int =\n            if not ((n and 1) != 0): return 2\n            if isprime(n): return n\n            const m = 128\n            while true:\n                var x, ys, q, r, g = 1\n                var rnd, y = rand(0..n-3) + 2\n                proc f(x: int): int = (mul(x, x, n) + rnd) mod n\n                while g == 1:\n                    x = y\n                    for i in 0..<r: y = f(y)\n                    for k in countup(0, r-1, m):\n                        ys = y\n                        for _ in 0..<min(m, r-k):\n                            y = f(y)\n                            q = mul(q, abs(x-y), n)\n                        g = gcd(q, n)\n                        if g != 1: break\n                    r = r shl 1\n                if g == n:\n                    g = 1\n                    while g == 1:\n                        ys = f(ys)\n                        g = gcd(n, abs(x - ys))\n                if g < n:\n                    if isprime(g): return g\n                    elif isprime(n div g): return n div g\n                    return find_factor(g)\n    \n        proc primefactor*(n: int, sorted: bool = true): seq[int] =\n            var n = n\n            while n > 1 and not isprime(n):\n                var p = find_factor(n)\n                while n mod p == 0:\n                    result.add(p)\n                    n = n div p\n            if n > 1: result.add(n)\n            if sorted: return result.sorted\n    \n        proc primefactor_cnt*(n: int): Table[int, int] =\n            for p in primefactor(n):\n                if p in result: result[p] += 1\n                else: result[p] = 1\n        discard\n    proc divisor_naive(x: int, sorted: bool): seq[int] =\n        for i in 1..x:\n            if i*i > x: break\n            if x mod i == 0:\n                result.add(i)\n                if i*i != x:\n                    result.add(x div i)\n        if sorted: result.sort\n\n    proc divisor*(x: int, sorted: bool = true): seq[int] =\n        if x <= 1000_000: return divisor_naive(x, sorted)\n        var factor = primefactor(x).toCountTable.pairs.toSeq\n        var ans = newSeq[int](0)\n        proc dfs(d, x: int) =\n            if d == factor.len:\n                ans.add(x)\n                return\n            var mul = 1\n            for i in 0..factor[d][1]:\n                dfs(d+1, x*mul)\n                if i != factor[d][1]: mul *= factor[d][0]\n        dfs(0, 1)\n        if sorted: ans.sort\n        return ans\n    discard\n"

ImportExpand "cplib/math/powmod.nim" <=== ""


var t = stdin.readLine.parseint
var ans = newSeq[int](0)
for _ in 0..<t:
    var n = stdin.readLine.parseint
    while n mod 2 == 0: n = n div 2
    while n mod 5 == 0: n = n div 5
    if n == 1:
        ans.add(1)
        continue
    for p in divisor(euler_phi(n)):
        if powmod(10, p, n) == 1:
            ans.add(p)
            break
echo ans.join("\n")