#include <bits/stdc++.h>
using namespace std;
long long ksj(long long a, long long b, long long p) {
  long long ans = 0;
  long long base = a;
  while (b) {
    if (b & 1) ans = (ans + base) % p;
    base = (base + base) % p;
    b >>= 1;
  }
  return ans;
}
long long ksm(long long a, long long b, long long p) {
  long long ans = 1;
  long long base = a;
  while (b) {
    if (b & 1) ans = ksj(ans, base, p) % p;
    base = ksj(base, base, p) % p;
    b >>= 1;
  }
  return ans;
}
long long mos[5]{-1, 0, 1, 3, 2};
int main() {
  long long t;
  cin >> t;
  while (t--) {
    long long a;
    cin >> a;
    long long tp = 1;
    long long n = to_string(a).length();
    for (long long m = 0;; m++) {
      long long x = a;
      long long mod = 1ll << (n + m);
      if (x % mod != 0) x = x + mod - x % mod;
      if (x % 5 == 0) x = x + mod;
      if (x % mod == 0 && x % 5 != 0 && x - a < tp) {
        long long y = x >> (n + m);
        long long t = mos[y % 5];
        long long ts = 5;
        for (long long i = 1; i < n + m; i++) {
          while (ksm(2, t, ts * 5) != y % (ts * 5)) t += ts / 5 * 4;
          ts *= 5;
        }
        cout << t + n + m << endl;
        break;
      }
      a *= 10;
      tp *= 10;
    }
  }
}
