#include <bits/stdc++.h>
using namespace std;
long long int mul(long long int a, long long int b, long long int c) {
  return (((long long int)a * b -
           (long long int)(a / (long double)c * b + 1e-5) * c) %
              c +
          c) %
         c;
}
long long int power(long long int n, long long int mod) {
  long long int ans = 1, t = 2;
  while (n) {
    if (n & 1) ans = mul(ans, t, mod);
    n >>= 1;
    t = mul(t, t, mod);
  }
  return ans;
}
template <class T>
inline void gn(T &x) {
  char c;
  while (c = getchar(), c < '0' || c > '9')
    ;
  for (x = 0; c >= '0' && c <= '9';
       x = (x << 3) + (x << 1) + c - '0', c = getchar())
    ;
}
int main() {
  int n;
  long long int a;
  for (gn(n); n--;) {
    gn(a);
    a *= 1000000;
    a = a + (1 << 17) - a % (1 << 17);
    if (a % 10 == 0) a += (1 << 17);
    long long int res = 500, mid = 10, stp = 1;
    for (int i = 0; i < 17; i++) {
      while (power(res, mid) != a % mid) res += stp;
      if (i)
        stp *= 5;
      else
        stp *= 4;
      mid = (mid << 3) + (mid << 1);
    }
    cout << res << endl;
  }
  return 0;
}
