#include <bits/stdc++.h>
using namespace std;
long long mul(long long a, long long b, long long p) {
  long long s = 0;
  while (b) {
    if (b & 1) s = (s + a) % p;
    a = (a + a) % p;
    b >>= 1;
  }
  return s;
}
long long ksm(long long a, long long b, long long p) {
  long long s = 1;
  while (b) {
    if (b & 1) s = mul(s, a, p);
    a = mul(a, a, p);
    b >>= 1;
  }
  return s;
}
int main() {
  long long n;
  cin >> n;
  while (n--) {
    long long a;
    cin >> a;
    long long n = to_string(a).length();
    for (long long m = 0;; m++) {
      long long b = ((1 << n + m) - a % (1 << n + m)) % (1 << n + m);
      if ((a + b) % 5 == 0) b += 1 << n + m;
      if (b < pow(10, m)) {
        long long x = (a + b) >> n + m, d = -1;
        for (long long i = 0; i < 5; i++)
          if ((1 << i) % 5 == x % 5) {
            d = i;
            break;
          }
        for (long long i = 2, p = 5; i <= n + m; i++) {
          long long phi = p / 5 * 4;
          p *= 5;
          for (long long k = 0; k < 5; k++)
            if (ksm(2, d + k * phi, p) == x % p) {
              d += k * phi;
              break;
            }
        }
        cout << d + n + m << '\n';
        break;
      }
      a *= 10;
    }
  }
  return 0;
}
