#include <bits/stdc++.h>
using namespace std;
long long Mul(long long x, long long y, long long mod) {
  long long res = 0;
  for (; x; x >>= 1, y = (y << 1) % mod)
    if (x & 1) res = (res + y) % mod;
  return res;
}
long long pow(long long x, long long k, long long mod) {
  long long sum = 1;
  for (; k; k >>= 1, x = Mul(x, x, mod))
    if (k & 1) sum = Mul(sum, x, mod);
  return sum;
}
long long Calc(int al, long long y) {
  long long g = -1, phi = 4, mod = 5;
  for (int i = 0; i < 4; ++i)
    if ((1 << i) % 5 == y % 5) g = i;
  for (int i = 2; i <= al; ++i, phi *= 5) {
    mod *= 5;
    for (int j = 0; j < 5; ++j)
      if (pow(2, g + j * phi, mod) == y % mod) {
        g += j * phi;
        break;
      }
  }
  return g;
}
int main() {
  int T, n;
  for (scanf("%d", &T); T; --T) {
    long long a, mx = 1;
    scanf("%lld", &a);
    n = 0;
    for (long long s = a; s; s /= 10) ++n;
    for (int m = 0;; ++m, a *= 10, mx *= 10) {
      long long b = 0;
      if (a % (1LL << n + m)) b = (1LL << n + m) - a % (1LL << n + m);
      if ((a + b) % 5 == 0) b += 1LL << n + m;
      if (b >= mx) continue;
      long long s = Calc(n + m, (a + b) >> n + m);
      printf("%lld\n", n + m + s);
      break;
    }
  }
  return 0;
}
