#include <bits/stdc++.h>
using namespace std;
long long T, n, ans, now, p1[20], p2[20], p0[20];
long long mul(long long a, long long b, long long res = 0) {
  for (; b; b >>= 1, a = (a + a) % 1000000000000000000)
    if (b & 1) res = (res + a) % 1000000000000000000;
  return res;
}
long long power(long long a, long long b, long long res = 1) {
  for (; b; b >>= 1, a = mul(a, a))
    if (b & 1) res = mul(res, a);
  return res;
}
long long quickmi(long long a, long long b) {
  long long t = 1;
  while (b) {
    if (b & 1) t = mul(t, a);
    a = mul(a, a);
    b >>= 1;
  }
  return t;
}
int main() {
  p1[0] = p0[0] = 1;
  p0[1] = 4;
  for (int i = 1; i <= 18; i++) p1[i] = p1[i - 1] * 10ll;
  for (int i = 2; i <= 18; i++) p0[i] = p0[i - 1] * 5ll;
  for (int i = 0; i <= 18; i++) p2[i] = power(2, p0[i]);
  scanf("%lld", &T);
  while (T--) {
    scanf("%lld", &n);
    n = n * 1000000ll / 131072ll + 1;
    if (n % 5 == 0) n++;
    n *= 131072;
    ans = 1000;
    now = power(2, ans);
    for (int i = 1; p1[i - 1] <= n; i++)
      while ((now - n) % p1[i] != 0)
        now = mul(now, p2[i - 1]), ans += p0[i - 1];
    printf("%lld\n", ans);
  }
  return 0;
}
