#include <bits/stdc++.h>
using namespace std;
int len(long long x) {
  int a = 0;
  for (; x; a++, x /= 10)
    ;
  return a;
}
long long mul(long long x, long long y, long long mo) {
  long long anw = 0;
  for (; y > 0; y >>= 1, x = (x << 1) % mo)
    if (y & 1) (anw += x) %= mo;
  return anw;
}
long long qsm(long long x, long long y, long long mo) {
  long long anw = 1;
  for (; y > 0; y >>= 1, x = mul(x, x, mo))
    if (y & 1) anw = mul(anw, x, mo);
  return anw;
}
inline void read(int &x) {
  static char c;
  for (c = getchar(); !('0' <= c && c <= '9'); c = getchar())
    ;
  for (x = 0; ('0' <= c && c <= '9'); c = getchar()) x = x * 10 + c - 48;
}
inline void read(long long &x) {
  static char c;
  for (c = getchar(); !('0' <= c && c <= '9'); c = getchar())
    ;
  for (x = 0; ('0' <= c && c <= '9'); c = getchar()) x = x * 10 + c - 48;
}
void write(long long x) {
  if (x < 10) {
    putchar('0' + x);
    return;
  }
  write(x / 10);
  putchar('0' + x % 10);
}
inline void writeln(long long x) {
  if (x < 0) putchar('-'), x *= -1;
  write(x);
  putchar('\n');
}
long long n, l, x, T, tp, mo, y, t, k, p5;
int main() {
  read(T);
  while (T--) {
    read(k);
    n = len(k);
    tp = 1;
    for (int m = 0;; m++) {
      x = k;
      mo = 1ll << (n + m);
      if (x % mo) x += mo - x % mo;
      if (!(x % 5)) x += mo;
      if ((!(x % mo)) && x % 5 && x - k < tp) {
        y = x >> (n + m);
        t = 0;
        if (y % 5 == 0) t = -1;
        if (y % 5 == 1) t = 0;
        if (y % 5 == 2) t = 1;
        if (y % 5 == 3) t = 3;
        if (y % 5 == 4) t = 2;
        p5 = 5;
        for (int i = 1; i < n + m; i++) {
          while (qsm(2, t, p5 * 5) != y % (p5 * 5)) t += p5 / 5 * 4;
          p5 *= 5;
        }
        writeln(t + n + m);
        break;
      }
      k *= 10, tp *= 10;
    }
  }
}
