You are given n positive integers a_1, a_2, ..., a_{n}.

For every a_{i} you need to find a positive integer k_{i} such that the decimal notation of 2^{k}_{i} contains the decimal notation of a_{i} as a substring among its last min(100, length(2^{k}_{i})) digits. Here length(m) is the length of the decimal notation of m.

Note that you don't have to minimize k_{i}. The decimal notations in this problem do not contain leading zeros.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 2 000) — the number of integers a_{i}.

Each of the next n lines contains a positive integer a_{i} (1 ≤ a_{i} < 10^11).


-----Output-----

Print n lines. The i-th of them should contain a positive integer k_{i} such that the last min(100, length(2^{k}_{i})) digits of 2^{k}_{i} contain the decimal notation of a_{i} as a substring. Integers k_{i} must satisfy 1 ≤ k_{i} ≤ 10^50.

It can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them.


-----Examples-----
Input
2
8
2

Output
3
1

Input
2
3
4857

Output
5
20

Difficulty: interview

Starter code:

Solutions:
def dlog(x, n):
  bigMod = 5 ** n
  ans = [None, 0, 1, 3, 2][x % 5]
  val = 2 ** ans % bigMod
  mod, phi = 5, 4
  phiVal = 2 ** phi % bigMod
  for i in range(2, n + 1):
    nextMod = mod * 5
    while val % nextMod != x % nextMod:
      val = val * phiVal % bigMod
      ans += phi
    phi *= 5
    phiVal = (phiVal *
              phiVal % bigMod *
              phiVal % bigMod *
              phiVal % bigMod *
              phiVal % bigMod)
    mod = nextMod
  return ans

def main():
  inp = input()
  n = len(inp)
  a = int(inp)
  for m in range(n + 1):
    l = a * 10 ** m
    x, mod = l, 2 ** (n + m)
    if x % mod != 0:
      x += mod - x % mod
    if x % 5 == 0:
      x += mod
    if x < l + 10 ** m:
      assert x % mod == 0 and x % 5 != 0
      x = x // mod
      mod = 5 ** (n + m)
      print(n + m + dlog(x % mod, n + m))
      return
  assert False

def __starting_point():
  cnt = int(input())
  for i in range(cnt):
    main()
__starting_point()



def dlog(x, n):
    bigMod = 5 ** n
    ans = [None, 0, 1, 3, 2][x % 5]
    val = 2 ** ans % bigMod
    mod, phi = 5, 4
    phiVal = 2 ** phi % bigMod
    for i in range(2, n + 1):
        nextMod = mod * 5
        while val % nextMod != x % nextMod:
            val = val * phiVal % bigMod
            ans += phi
        phi *= 5
        phiVal = (phiVal *
                  phiVal % bigMod *
                  phiVal % bigMod *
                  phiVal % bigMod *
                  phiVal % bigMod)
        mod = nextMod
    return ans


def main():
    inp = input()
    n = len(inp)
    a = int(inp)

    for m in range(n + 1):
        l = a * 10 ** m
        x, mod = l, 2 ** (n + m)
        if x % mod != 0:
            x += mod - x % mod
        if x % 5 == 0:
            x += mod
        if x < l + 10 ** m:
            x = x // mod
            mod = 5 ** (n + m)
            print(n + m + dlog(x % mod, n + m))
            return

def __starting_point():
    cnt = int(input())
    for i in range(cnt):
        main()

__starting_point()

 #Power substring 913G
def dlog(x, n):
  bigMod = 5 ** n
  ans = [None, 0, 1, 3, 2][x % 5]
  val = 2 ** ans % bigMod
  mod, phi = 5, 4
  pval = 2 ** phi % bigMod
  for i in range(2, n + 1):
    nextMod = mod * 5
    while val % nextMod != x % nextMod:
      val = val * pval % bigMod
      ans += phi
    phi *= 5
    pval = (pval * pval % bigMod * pval % bigMod *
              pval % bigMod *
              pval % bigMod)
    mod = nextMod
  return ans

def main():
  inp = input()
  n = len(inp)
  a = int(inp)
  for m in range(n + 1):
    l = a * 10 ** m
    x, mod = l, 2 ** (n + m)
    if x % mod != 0:
      x += mod - x % mod
    if x % 5 == 0:
      x += mod
    if x < l + 10 ** m:
      assert x % mod == 0 and x % 5 != 0
      x = x // mod
      mod = 5 ** (n + m)
      print(n + m + dlog(x % mod, n + m))
      return
  assert False

def __starting_point():
  cnt = int(input())
  for i in range(cnt):
    main()
__starting_point()

def dlog(x, n):
  bigMod = 5 ** n
  ans = [None, 0, 1, 3, 2][x % 5]
  val = 2 ** ans % bigMod
  mod, phi = 5, 4
  phiVal = 2 ** phi % bigMod
  for i in range(2, n + 1):
    nextMod = mod * 5
    while val % nextMod != x % nextMod:
      val = val * phiVal % bigMod
      ans += phi
    phi *= 5
    phiVal = (phiVal *
              phiVal % bigMod *
              phiVal % bigMod *
              phiVal % bigMod *
              phiVal % bigMod)
    mod = nextMod
  return ans

def main():
  inp = input()
  n = len(inp)
  a = int(inp)
  for m in range(n + 1):
    l = a * 10 ** m
    x, mod = l, 2 ** (n + m)
    if x % mod != 0:
      x += mod - x % mod
    if x % 5 == 0:
      x += mod
    if x < l + 10 ** m:
      assert x % mod == 0 and x % 5 != 0
      x = x // mod
      mod = 5 ** (n + m)
      print(n + m + dlog(x % mod, n + m))
      return
  assert False

def __starting_point():
  cnt = int(input())
  for i in range(cnt):
    main()
__starting_point()