#include <bits/stdc++.h>
using namespace std;
long long pwr(long long x, int y) {
  long long p = 1;
  while (y--) {
    p *= x;
  }
  return p;
}
long long add(long long x, long long y, long long md) {
  x = (x + y) % md;
  if (x < 0) {
    x += md;
  }
  return x;
}
void addeq(long long &x, long long y, long long md) { x = add(x, y, md); }
long long subtr(long long x, long long y, long long md) {
  x = (x - y) % md;
  if (x < 0) {
    x += md;
  }
  return x;
}
long long mult(long long x, long long y, long long md) {
  const static int BLOCK = 1e6;
  long long yl = y / BLOCK, yr = y % BLOCK;
  return add(yr * x % md, yl * x % md * BLOCK % md, md);
}
void multeq(long long &x, long long y, long long md) { x = mult(x, y, md); }
long long pwr(long long x, long long y, long long md) {
  long long res = 1;
  for (; y; y >>= 1) {
    if (y & 1) {
      multeq(res, x, md);
    }
    multeq(x, x, md);
  }
  return res;
}
long long pwr5[20];
void precomp() {
  pwr5[0] = 1;
  for (int i = 1; i < 20; i++) {
    pwr5[i] = pwr5[i - 1] * 5;
  }
}
long long A;
int N, M;
long long go() {
  N = to_string(A).size();
  M = 17 - N;
  int opwr = 1 << 17;
  long long fro = pwr(10, M) * A;
  ;
  long long rem = fro + subtr(0, fro, opwr);
  if (rem % 5 == 0) {
    rem += opwr;
  };
  rem %= pwr5[17];
  ;
  long long curv = rem;
  long long curb = (pwr5[17] + 1) / 2;
  long long modp516 = 0;
  for (int i = 2; i <= 17; i++) {
    ;
    for (int j = 0; j < 5; j++) {
      ;
      if (pwr(curv % pwr5[i], 4, pwr5[i]) == 1) {
        break;
      }
      multeq(curv, curb, pwr5[17]);
      modp516 += pwr5[i - 2];
    };
    curb = pwr(curb, 5, pwr5[17]);
    ;
  };
  int mod4;
  if (rem % 5 == 1) {
    mod4 = 0;
  } else if (rem % 5 == 2) {
    mod4 = 1;
  } else if (rem % 5 == 4) {
    mod4 = 2;
  } else if (rem % 5 == 3) {
    mod4 = 3;
  } else {
    assert(!"Divisible by 5!?");
  }
  long long res = modp516;
  while (res < 100 || res % 4 != mod4) {
    res += pwr5[16];
  }
  return res;
}
int main() {
  precomp();
  int nq;
  scanf("%d", &nq);
  for (int qi = 0; qi < nq; qi++) {
    scanf("%lld", &A);
    printf("%lld\n", go());
  }
}
