#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
const long long ooo = 9223372036854775807ll;
const int _cnt = 1000 * 1000 + 7;
const int _p = 1000 * 1000 * 1000 + 7;
const int N = 200005;
const double PI = acos(-1.0);
const double eps = 1e-9;
int o(int x) { return x % _p; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
void file_put() {
  freopen("filename.in", "r", stdin);
  freopen("filename.out", "w", stdout);
}
long long Mul(long long a, long long b, long long p) {
  long long ans = 0;
  for (; b; b >>= 1, (a += a) %= p)
    if (b & 1) (ans += a) %= p;
  return ans;
}
long long Pow(long long x, long long k, long long p) {
  long long ans = 1;
  for (; k; k >>= 1, x = Mul(x, x, p))
    if (k & 1) ans = Mul(ans, x, p);
  return ans;
}
int T, Log2[] = {-1, 0, 1, 3, 2};
long long x, y, a, b, c, t, k, p, n;
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%I64d", &a);
    n = to_string(a).length();
    for (int m = 0; m <= 10; m++, a *= 10) {
      b = ((-a) & ((1ll << n + m) - 1));
      if ((a + b) % 5 == 0) b += (1ll << n + m);
      if (!m && !b || to_string(b).length() <= m) {
        x = a + b, y = x >> n + m, t = Log2[y % 5], p = 5;
        for (int i = 2; i <= n + m; i++, p *= 5)
          while (Pow(2, t, p * 5) != y % (p * 5)) t += p / 5 * 4;
        t += n + m;
        break;
      }
    }
    printf("%I64d\n", t);
  }
  return 0;
}
