package main
import (
  "fmt"
)
func e(x uint64) string {
	if x == 0 {
		return ""
	}
	return e(x >> 1) + string((x & 1) + '0')
}
func main() {
  var n, x int
  var ok bool
  fmt.Scanf("%d", &n)
  for i := 0; i < n; i++ {
    fmt.Scanf("%d", &x)
    m := make(map[int]uint64)
    m[1 % x] = 1
    _, ok = m[10 % x]
    if !ok {
      m[10 % x] = 2
    }
    _, ok = m[11 % x]
    if !ok {
      m[11 % x] = 3
    }
    a := uint64(2)
    r := 10 % x
    _, ok = m[0]
    for !ok {
      a = a << 1
      r = (r * 10) % x
      mc := make(map[int]uint64)
      for k, v := range m {
        mc[k] = v
      }
      _, ok = m[r]
      if !ok {
        m[r] = a
      }
      if r == 0 {
        break
      }
      for k, v := range mc {
        nr := (r + k) % x
        _, ok = m[nr]
        if !ok {
          m[nr] = a + v
          if nr == 0 {
            break
          }
        }
      }
      _, ok = m[0]
    }
    fmt.Printf("%s\n", e(m[0]))
  }
}