#include <bits/stdc++.h>
using namespace std;
template <class T>
void chkmax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
void chkmin(T &a, T b) {
  if (a > b) a = b;
}
long long mod_mul(long long x, long long y, long long mod) {
  if (x == 0 || y == 0) return 0;
  x = (x + mod) % mod, y = (y + mod) % mod;
  long long ret = 0;
  while (x) {
    ret = (ret + (x & 1) * y) % mod;
    y = (y << 1) % mod;
    x >>= 1;
  }
  return (ret + mod) % mod;
}
long long expmod(long long a, long long b, long long n) {
  long long re = 1, y = a % n;
  while (b) {
    if (b % 2) re = mod_mul(re, y, n);
    b >>= 1, y = mod_mul(y, y, n);
  }
  return re;
}
long long gcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  } else {
    long long tp, bx, by;
    tp = gcd(b, a % b, x, y);
    bx = x, by = y;
    y = bx - (a / b) * by, x = by;
    return tp;
  }
}
long long inv(long long a, long long n) {
  long long x, y, tp;
  tp = gcd(a, n, x, y);
  if (tp == 1)
    return (((x) % (n) + (n)) % (n));
  else
    return -1;
}
long long fv[20];
long long lg[10] = {0, 0, 1, 3, 2};
long long func(long long b, long long n) {
  if (n == 1) return lg[b % 5];
  long long tmp = func(b, n - 1);
  long long r = expmod(2, tmp, fv[n]);
  int t = 0;
  while ((b % fv[n]) != mod_mul(r, 1 + 3 * fv[n - 1] * t, fv[n])) t++;
  tmp += 4 * fv[n - 2] * t;
  return tmp;
}
int n;
long long a;
int main() {
  fv[0] = 1;
  for (int i = 1; i < 19; i++) fv[i] = fv[i - 1] * 5;
  scanf("%d", &n);
  while (n--) {
    scanf("%I64d", &a);
    int l = (int)log10(a) + 1;
    long long b = (a + 1) * 1000000 - 1;
    l += 6;
    b >>= l;
    long long ans;
    if (b % 5 == 0) b--;
    ans = func(b, l);
    cout << ans + l << endl;
  }
  return 0;
}
