#include <bits/stdc++.h>
using namespace std;
clock_t __stt;
inline void TStart() { __stt = clock(); }
inline void TReport() {
  printf("\nCurrent Case Taken Time : %.3lf sec\n",
         (double)(clock() - __stt) / CLOCKS_PER_SEC);
}
template <typename T>
T MIN(T a, T b) {
  return a < b ? a : b;
}
template <typename T>
T MAX(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
T ABS(T a) {
  return a > 0 ? a : (-a);
}
template <typename T>
void UMIN(T &a, T b) {
  if (b < a) a = b;
}
template <typename T>
void UMAX(T &a, T b) {
  if (b > a) a = b;
}
long long P, Q, M, pow5[25];
int d, n;
long long phi5(int e) { return pow5[e] - pow5[e] / 5ll; }
long long slowmul(long long A, long long B, long long M) {
  long long R = 0ll;
  while (B) {
    if (B & 1ll) {
      R = R + A;
      if (R >= M) R -= M;
    }
    B >>= 1ll;
    A *= 2ll;
    if (A >= M) A -= M;
  }
  return R;
}
long long powM(long long V, long long T, long long M) {
  long long R = 1ll;
  V %= M;
  while (T) {
    if (T & 1ll) R = slowmul(R, V, M);
    T >>= 1ll;
    V = slowmul(V, V, M);
  }
  return R;
}
void solve() {
  int i, j, k;
  scanf("%lld", &P);
  pow5[0] = 1ll;
  for (i = 1; i < 25; ++i) pow5[i] = pow5[i - 1] * 5ll;
  Q = P;
  for (d = 0; Q; Q /= 10ll, ++d)
    ;
  M = 1ll;
  for (n = 0;; ++n) {
    long long x = P * M, L = 1ll << (long long)(n + d), Y;
    Q = (L - x % L) % L;
    while (Q < M && !((x + Q) % 5ll)) {
      Q += L;
    }
    if (Q >= M) {
      M *= 10ll;
      continue;
    }
    Y = (x + Q) / L;
    long long nk = 0ll;
    for (i = 1; i <= n + d; ++i) {
      while (powM(2, nk, pow5[i]) != Y % pow5[i]) {
        nk += phi5(i - 1);
      }
    }
    printf("%lld\n", nk + (long long)n + (long long)d);
    return;
  }
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}
