#include <bits/stdc++.h>
using namespace std;
long long A, B, C;
int T, le = 0;
inline long long M(long long x, long long mod) {
  return (x >= mod) ? (x - mod) : x;
}
inline long long mul(long long x, long long y, long long mod) {
  long long res = 0;
  while (y) {
    if (y & 1) res = M(res + x, mod);
    y >>= 1;
    x = M(x + x, mod);
  }
  return res;
}
inline long long ksm(long long x, long long y, long long mod) {
  long long res = 1;
  while (y) {
    if (y & 1) res = mul(res, x, mod);
    y >>= 1;
    x = mul(x, x, mod);
  }
  return res;
}
inline pair<long long, long long> Ask(long long x, int o, int p, long long mod,
                                      long long mo, long long &y,
                                      long long &ph) {
  if (mod == 1) {
    ph = 1;
    y = o;
    return make_pair(1, 0);
  }
  int i;
  long long v, v1, v2, k;
  pair<long long, long long> p1 = Ask(x, o, p, mod / p, mo, v1, ph);
  v = p1.first;
  v2 = x % mod;
  for (i = 0; i < p; i++, v = mul(v, v1, mo))
    if ((v % mod) == v2) break;
  k = i * ph + p1.second;
  ph *= (mod == p) ? (--p) : p;
  for (y = 1; p; p--) y = mul(y, v1, mo);
  return make_pair(v, k);
}
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%lld", &A);
    B = A;
    le = 0;
    while (B) ++le, B /= 10;
    int i;
    long long k, y, ph;
    A *= 1000000;
    le += 6;
    C = 1;
    for (i = 1; i <= le; i++) C *= 2;
    for (k = (A - 1) / C + 1; k % 5 == 0; k++)
      ;
    B = k;
    C = 1;
    for (i = 1; i <= le; i++) C *= 5;
    printf("%lld\n", Ask(B, 2, 5, C, C, y, ph).second + le);
  }
  return 0;
}
