#include <bits/stdc++.h>
using namespace std;
void mul(long long &x, long long y, long long MOD) {
  long long res = 0;
  while (y) {
    if (y & 1) (res += x) %= MOD;
    (x += x) %= MOD;
    y >>= 1;
  }
  x = res;
}
long long mpow(long long x, long long n, long long MOD = 1e18L) {
  long long res = 1;
  while (n) {
    if (n & 1) mul(res, x, MOD);
    n >>= 1;
    mul(x, x, MOD);
  }
  return res;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    long long a;
    scanf("%lld", &a);
    long long x = mpow(10, 6) * a;
    long long base = mpow(2, 17);
    x = (x + base - 1) / base * base;
    if (x % 5 == 0) x += base;
    long long y = x / base;
    long long k = 0, phi = 1;
    for (int i = 1; i <= 17; ++i) {
      for (int j = 0; j < 5; ++j) {
        long long kk = (k + j * phi) % mpow(5, i);
        if (mpow(2, kk, mpow(5, i)) == y % mpow(5, i)) {
          k = kk;
          break;
        }
      }
      phi *= (i == 1 ? 4 : 5);
    }
    printf("%lld\n", k + 17);
  }
}
