#include <bits/stdc++.h>
using namespace std;
const int C = 5000001, D = 17, E = 124001, F = 5000001, V = 1 << 20;
using ll = long long;
inline ll neo_mul(ll a, ll b, ll M) {
  return (((a * (b / 1000000)) % M) * 1000000 + a * (b % 1000000)) % M;
}
inline ll pow(ll a, ll b, ll M) {
  ll c = 1;
  while (b > 0) {
    if (b % 2 == 1) c = neo_mul(c, a, M);
    b /= 2;
    a = neo_mul(a, a, M);
  }
  return c;
}
std::pair<ll, ll> Euclid(ll a, ll b) {
  ll x1 = 0, x2 = 1, y1 = 1, y2 = 0, q = a / b, r = a - q * b, x, y, wynn;
  x = 1, y = y2 - (q - 1) * y1;
  while (r != 0) {
    a = b, b = r;
    x = x2 - q * x1, x2 = x1, x1 = x;
    y = y2 - q * y1, y2 = y1, y1 = y;
    wynn = r, q = a / b, r = a - q * b;
  }
  return std::make_pair(x, y);
}
ll invert(ll a, ll M) {
  ll x = Euclid(a, M).first;
  if (x < 0) return x + M;
  return x;
}
template <class T>
T CRT_Solver(T c1, T s1, T c2, T s2) {
  T crv, kp, res, sol, z, lcm;
  pair<T, T> kl = Euclid(s1, s2);
  kp = kl.first;
  res = 1;
  lcm = (s1 * s2) / res;
  if ((c2 - c1) % res != 0) return -1;
  crv = (c2 - c1) / res;
  kp = neo_mul(kp, crv, lcm);
  sol = (neo_mul(kp, s1, lcm) + c1) % lcm;
  if (sol < 0) sol += lcm;
  return sol;
}
ll values[D], res[D], mods[D];
ll discr_log_pohlig_hellman(ll a, ll y, ll M, ll toth, ll dv[], ll s[],
                            int ln) {
  int i, j, ij;
  ll tmp_res, tmp_exp, tmp_y, v1, v2;
  for (i = 0; i < ln; i++) {
    res[i] = 0;
    tmp_exp = 1;
    tmp_y = y;
    for (j = 0; j < dv[i]; j++) values[j] = pow(a, j * (toth / dv[i]), M);
    for (j = 0; j < s[i]; j++) {
      tmp_res = pow(tmp_y, toth / (tmp_exp * dv[i]), M);
      for (ij = 0; ij < dv[i]; ij++) {
        if (values[ij] == tmp_res) break;
      }
      tmp_y = neo_mul(tmp_y, invert(pow(a, tmp_exp * ij, M), M), M);
      res[i] += tmp_exp * ij;
      tmp_exp *= dv[i];
    }
    mods[i] = tmp_exp;
  }
  v1 = res[0], v2 = mods[0];
  for (i = 1; i < ln; i++) {
    v1 = CRT_Solver(v1, v2, res[i], mods[i]);
    v2 = v2 * mods[i];
  }
  return v1;
}
bool mark_of_death[V];
ll dv[D], s[D];
int main() {
  int i = 0, t;
  ll pw_5 = 1, pw_2 = 1 << D, a, mover = 1000000, lefty, toth;
  for (i = 1; i <= D; i++) pw_5 *= 5;
  for (i = 1; i <= D; i++) mark_of_death[1 << i] = 1;
  dv[0] = 2, dv[1] = 5;
  s[0] = 2, s[1] = D - 1;
  toth = 4 * (pw_5 / 5);
  scanf("%d", &t);
  while (t--) {
    scanf("%lld", &a);
    lefty = mover * a;
    lefty = (lefty / pw_2 + (lefty % pw_2 == 0 ? 0 : 1)) * pw_2;
    for (; lefty % 5 == 0 ||
           (lefty % pw_5 < V && mark_of_death[lefty % pw_5] == 1);
         lefty += pw_2)
      ;
    printf("%lld\n",
           discr_log_pohlig_hellman(2, lefty % pw_5, pw_5, toth, dv, s, 2));
  }
  return 0;
}
