#include <bits/stdc++.h>
using namespace std;
long long dw(long long a, long long b) {
  if (a >= b) return a - b;
  return a;
}
long long mul(long long x, long long y, long long mod) {
  long long res = 0;
  if (x < y) swap(x, y);
  while (y) {
    if (y & 1) res = dw(res + x, mod);
    x = dw(2 * x, mod);
    y /= 2;
  }
  return res;
}
long long mpow(long long x, long long n, long long mod) {
  long long res = 1;
  while (n) {
    if (n & 1) res = mul(res, x, mod) % mod;
    x = mul(x, x, mod);
    n /= 2;
  }
  return res;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int T;
  cin >> T;
  for (int test = 1; test <= T; ++test) {
    long long a;
    cin >> a;
    long long pw10 = 10, pw5 = 5, pw = 1;
    while (pw10 <= a) {
      pw10 *= 10;
      pw5 *= 5;
      ++pw;
    }
    for (long long t = 1, p5 = 5, p10 = 10;; ++t, p5 *= 5, p10 *= 10) {
      assert(t < 10);
      long long p2 = (1LL << (t + pw));
      long long rem = p2 - (a % p2) * (p10 % p2) % p2;
      while (rem < p10 && rem % 5 == 0) {
        rem += p2;
      }
      if (rem < p10) {
        long long mod = p5 * pw5;
        long long rem5 = (rem + (a << t) % pw5 * p5) % mod;
        assert(rem5 % 5);
        long long k = 0;
        while ((1LL << k) % 5 != rem5 % 5) ++k;
        for (long long i = 2, curp5 = 25; i <= pw + t; ++i, curp5 *= 5) {
          while (mpow(2, k, curp5) != rem5 % curp5) {
            k += curp5 / 5 / 5 * 4;
          }
        }
        while (k < t + pw) {
          k += mod / 5 * 4;
        }
        cout << k << endl;
        assert(mpow(2, k, p2) == (a * p10 + rem) % p2);
        assert(mpow(2, k, mod) == (a * p10 + rem) % mod);
        break;
      }
    }
  }
  return 0;
}
