#include <bits/stdc++.h>
using namespace std;
int T;
long long x;
inline long long Mul(long long a, long long b, long long Mod) {
  return __int128(a) * b % Mod;
}
inline long long ksm(long long a, long long b, long long Mod) {
  long long ans = 1;
  for (; b; b >>= 1, a = Mul(a, a, Mod))
    if (b & 1) ans = Mul(ans, a, Mod);
  return ans;
}
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%lld", &x);
    long long y = x, t = 1;
    int len = 0;
    while (y) y /= 10, ++len;
    for (int i = (0); i <= (60); ++i) {
      long long d = 1ll << (i + len), z = x;
      if (z % d) z += d - z % d;
      if (!(z % 5)) z += d;
      if (z - x < t) {
        z >>= i + len;
        long long now = 0, x = 1, g = 5;
        for (int j = (0); j <= (3); ++j) {
          if (x == z % 5) {
            now = j;
            break;
          }
          x = x * 2 % 5;
        }
        for (int j = (2); j <= (i + len); ++j) {
          for (int k = (0); k <= (4); ++k)
            if (ksm(2, now, g * 5) != z % (g * 5))
              now += g / 5 * 4;
            else
              break;
          g *= 5;
        }
        printf("%lld\n", now + i + len);
        break;
      }
      x *= 10;
      t *= 10;
    }
  }
  return 0;
}
