#include <bits/stdc++.h>
using namespace std;
char a[15];
long long fac1[20], fac2[20], g[20], r[100010];
vector<int> e[100010];
inline long long times(long long first, long long second, long long mod) {
  long long t = 0;
  while (second) {
    t = (first * (second & 63) + t) % mod;
    first = first * 64 % mod;
    second >>= 6;
  }
  return t;
}
long long power(long long k, long long mod) {
  if (!k) return 1;
  long long t = power(k / 2, mod);
  if (mod <= 1000000000ll)
    t = t * t % mod;
  else
    t = times(t, t, mod);
  if (k & 1) t = (t + t) % mod;
  return t;
}
long long solve(long long k, long long q, int d, int n) {
  if (!n) return k;
  if ((q / fac1[d - 1] + a[n]) % 2) return -1;
  long long w1 = g[d], w2 = q;
  for (int i = 0; i < 5; i++) {
    if (w2 / fac1[d - 1] % 10 == a[n] - '0')
      return solve(fac2[d] * i + k, w2, d + 1, n - 1);
    w2 = times(w2, w1, fac1[17]);
  }
  return -1;
}
int main() {
  fac1[0] = 1;
  for (int i = 1; i <= 18; i++) fac1[i] = fac1[i - 1] * 10;
  fac2[3] = 20;
  for (int i = 4; i <= 18; i++) fac2[i] = fac2[i - 1] * 5;
  for (int i = 4; i <= 18; i++) g[i] = power(fac2[i], fac1[17]);
  int T;
  scanf("%d", &T);
  long long t = 1 << 20;
  for (int i = 21; i <= 100000; i++) {
    t = t * 2 % fac1[17];
    r[i] = t;
    e[t / fac1[6] % 10].push_back(i);
  }
  while (T--) {
    scanf("%s", a + 1);
    int n = strlen(a + 1);
    int s = 0;
    for (vector<int>::iterator p = e[(a[n] - '0') % 10].begin();
         p != e[(a[n] - '0') % 10].end(); p++) {
      long long first = solve(*p, r[*p], 8, n - 1);
      s++;
      if (first != -1) {
        printf("%I64d\n", first);
        break;
      }
    }
  }
  return 0;
}
