#include <bits/stdc++.h>
using namespace std;
int t, n;
long long k, b, p, l, q, c, r;
inline long long mul(long long a, long long b, long long p) {
  long long u = 0;
  while (b > 0) {
    if (b & 1) u = (u + a) % p;
    a = (a + a) % p, b = b >> 1;
  }
  return u;
}
inline long long pows(long long u, long long v, long long p) {
  long long ans = 1;
  while (v > 0) {
    if (v & 1) ans = mul(ans, u, p);
    u = mul(u, u, p), v = v >> 1;
  }
  return ans;
}
int main() {
  cin >> t;
  while (t--) {
    cin >> k, p = k, q = 1, c = 1, n = 0;
    while (p > 0) p = p / 10, n++, q = q * 5;
    for (int m = 1; m <= 114514; m++) {
      l = (1ll << (n + m)) - 1, k = k * 10, b = (k & l) ^ l, q = q * 5,
      c = c * 10;
      if (b == l)
        b = 0;
      else
        b++;
      if ((k + b) % 5 == 0) b += l + 1;
      if (b > c) continue;
      long long w = (k + b) >> (n + m), r = 1, q = 2, sum = 0;
      for (int c = 1; c <= n + m; c++) {
        r = r * 5;
        long long t = pows(2, sum, r);
        if (t == 0) t = 1;
        long long z = 1;
        if (c > 1) {
          z = z * 4;
          for (int x = 2; x < c; x++) z = z * 5;
        }
        if (w % r > 0) {
          for (int x = 0; x <= 4; x++) {
            if (t == w % r) {
              sum += z * x;
              break;
            }
            t = mul(t, q, r);
          }
        }
        long long ct = 1;
        if (c == 1)
          for (int x = 1; x <= 4; x++) ct = mul(q, ct, r * 5);
        else
          for (int x = 0; x <= 4; x++) ct = mul(q, ct, r * 5);
        q = ct;
      }
      cout << sum + n + m << endl;
      break;
    }
  }
}
