#include <bits/stdc++.h>
using namespace std;
long long P = 1e18;
long long mulmod(long long x, long long y) {
  long long ans = 0;
  while (x) {
    if (x & 1) ans = (ans + y) % P;
    y = (y + y) % P;
    x /= 2;
  }
  return ans;
}
long long powmod(long long x, long long y = P / 5 * 4 - 1, long long p = P) {
  long long ans = 1;
  while (y) {
    if (y & 1) ans = mulmod(ans, x);
    x = mulmod(x, x);
    y >>= 1;
  }
  return ans;
}
long long mul10[19], mul2[19], mul2_[19], n;
int main() {
  for (int i = 0; i < 19; i++) mul10[i] = !i ? 1 : mul10[i - 1] * 10;
  mul2[0] = 1;
  mul2_[0] = 2;
  for (int i = 1; i < 19; i++)
    mul2_[i] = powmod(2, mul2[i] = (4 * ((mul10[i] >> i) / 5)));
  long long ori = 10000, ret = powmod(2, ori);
  scanf("%lld", &n);
  while (n--) {
    long long x, tmp;
    scanf("%lld", &x);
    x = x * 1000000 / 131072 + 1;
    if (x % 5 == 0) x++;
    x *= 131072;
    long long ans = ori, nw = ret;
    for (int i = 1; i < 18; i++)
      while ((x - nw) % mul10[i]) {
        nw = mulmod(nw, mul2_[i - 1]);
        ans += mul2[i - 1];
      }
    printf("%lld\n", ans);
  }
  return 0;
}
