#include <bits/stdc++.h>
using namespace std;
int T, n, m;
long long x, y, a, b;
long long calc(long long x, long long y, long long mod) {
  long long res = 0;
  while (y) {
    if (y & 1) res = res + x;
    x <<= 1;
    y >>= 1;
    if (x >= mod) x -= mod;
    if (res >= mod) res -= mod;
  }
  return res;
}
long long power(long long x, long long y, long long mod) {
  long long res = 1;
  x %= mod;
  while (y) {
    if (y & 1) res = calc(res, x, mod);
    x = calc(x, x, mod);
    y >>= 1;
  }
  return res;
}
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%lld", &a);
    long long t = a, mm = 1;
    n = 0;
    while (t) t /= 10, n++;
    for (m = 0;; m++, a *= 10, mm *= 10) {
      b = (-a) & ((1 << (n + m)) - 1);
      if ((a + b) % 5 == 0) b += 1 << (n + m);
      if (b >= mm) continue;
      x = a + b;
      y = x >> (n + m);
      long long p = 0;
      for (int i = 0; i < 4; i++)
        if (power(2, i, 5) == y % 5) p = i;
      long long s1 = 4, s2 = 5;
      for (int i = 2; i <= n + m; i++) {
        s2 *= 5;
        for (int j = 0; j < 5; j++)
          if (power(2, p + j * s1, s2) == y % s2) {
            p += j * s1;
            break;
          }
        s1 *= 5;
      }
      printf("%lld\n", p + n + m);
      break;
    }
  }
  return 0;
}
